Есть плоскость, разделенная сеткой на одинаковые клетки. Есть круг диаметром равным стороне клетки. Бросаем круг случайным образом на плоскость. Требуется определить среднее число клеток, которые этот круг частично накрывает. Должно быть что-то между 3 и 4. Теперь берем 3D простронство, разбитое на кубики и сферу. Далее — 4D, 5D, etc. Интересует прежде всего форма функции среднего количества пересечений гиперсферы с гиперкубами в зависимости от мерности пространства, то есть, что-то типа big-Oh notation, O(f(d)). Для наихудшего случая, 2D — четыре клетки, 3D — 8 кубиков, то есть, Theta(2**d). А вот какова формула для среднего, хотя-бы приблизительно?

Здравствуйте, McSeem2, Вы писали:

MS>Есть плоскость, разделенная сеткой на одинаковые клетки. Есть круг диаметром равным стороне клетки. Бросаем круг случайным образом на плоскость. Требуется определить среднее число клеток, которые этот круг частично накрывает. Должно быть что-то между 3 и 4. Теперь берем 3D простронство, разбитое на кубики и сферу. Далее — 4D, 5D, etc. Интересует прежде всего форма функции среднего количества пересечений гиперсферы с гиперкубами в зависимости от мерности пространства, то есть, что-то типа big-Oh notation, O(f(d)). Для наихудшего случая, 2D — четыре клетки, 3D — 8 кубиков, то есть, Theta(2**d). А вот какова формула для среднего, хотя-бы приблизительно?

Для 2D просто — 3+pi/4, далее не думаю, что сильно сложнее, но работа не позволяет .

Здравствуйте, McSeem2, Вы писали:

MS>Есть плоскость, разделенная сеткой на одинаковые клетки. Есть круг диаметром равным стороне клетки. Бросаем круг случайным образом на плоскость. Требуется определить среднее число клеток, которые этот круг частично накрывает. Должно быть что-то между 3 и 4. Теперь берем 3D простронство, разбитое на кубики и сферу. Далее — 4D, 5D, etc. Интересует прежде всего форма функции среднего количества пересечений гиперсферы с гиперкубами в зависимости от мерности пространства, то есть, что-то типа big-Oh notation, O(f(d)). Для наихудшего случая, 2D — четыре клетки, 3D — 8 кубиков, то есть, Theta(2**d). А вот какова формула для среднего, хотя-бы приблизительно?

Есть большое подозрение, что формула следующая:

d+1+(1-(d+1)/2^d)*V(d), где V(d)=pi^(d/2)/Г(1+d/2) - объем гиперсферы единичного радиуса, а Г - гамма ф-ция

Таким образом:

1 — 2
2 — 3+pi/4
3 — 4 + 2*pi/3

Строго доказывать формулу и строить графики — нет времени (работа )

Здравствуйте, McSeem2, Вы писали:

MS>Есть плоскость, разделенная сеткой на одинаковые клетки. Есть круг диаметром равным стороне клетки. Бросаем круг случайным образом на плоскость. Требуется определить среднее число клеток, которые этот круг частично накрывает. Должно быть что-то между 3 и 4. Теперь берем 3D простронство, разбитое на кубики и сферу. Далее — 4D, 5D, etc. Интересует прежде всего форма функции среднего количества пересечений гиперсферы с гиперкубами в зависимости от мерности пространства, то есть, что-то типа big-Oh notation, O(f(d)). Для наихудшего случая, 2D — четыре клетки, 3D — 8 кубиков, то есть, Theta(2**d). А вот какова формула для среднего, хотя-бы приблизительно?

Пусть сторона кубов и диаметр шара равны 1.
Центр шара равномерно распределен внутри куба. При этом шар может частично накрыть от 1 до 2^d кубов. Однако с ненулевой вероятностью он может накрыть только 2^d или (2^d-1) кубов — в остальных случаях центр шара пробегает многообразие размерности меньшей d (для примера — в двумерном случае круг накрывает 2 квадрата, когда его центр находится на кресте из отрезков параллельных сторонам и проходящих через центр квадрата).

Шар накрывает (2^d-1) кубов в случае, если его центр удален от всех углов куба более чем на 1, т.е. тогда, когда он находится внутри другого шара с радиусом (sqrt(d)-1)/2, центр которого совпадает с центром куба. Поэтому вероятность этого события равна объему пересечения куба с этим шаром. При d<5 этот шар целиком попадает в куб, и объем пересечения равен объему шара, а вот дальше — сложнее.
В любом случае, если вероятность накрыть (2^d-1) кубов равна P, а накрыть 2^d кубов (1-P), то матожидание равно
P*(2^d-1) + (1-P)*2^d = 2^d — P.
С ростом d значение P приближается к единице, т.е. асимптотика будет 2^d-1.

Поскольку объем d-мерного шара радиуса R равен
V(R)= R^d*pi^(d/2)/Г(d/2+1),
где Г — гамма-функция, то для d<5 имеем
P=V((sqrt(d)-1)/2).
В частности, при d=2 получаем V(R)=pi*R^2, т.е. P=pi*(3-2*sqrt(2))/4 и матожидание числа пересечений равно 4-P.

Здравствуйте, MichaelP, Вы писали:

MP>Для 2D просто — 3+pi/4, далее не думаю, что сильно сложнее, но работа не позволяет .

Да нет, именно что сложнее

Для 3-мерного случая 4+11pi/12

Для N-мерного

F(N)=SUM[n=0-N]{C(N,n)*(1/2)^n*V(n)}

где V(n) — объём единичного n-мерного шара

V(n) = pi^(n/2) / (n/2)!

(факториал нецелого — через гамма-функцию)

Если бы не было факториала в знаменателе V(n), мы бы имели просто

F(N)= (1+sqrt(pi)/2)^N ~ exp(kN)

Но он стервец есть, поэтому оценивать сложно.
После неких пассов руками у меня получилось для больших N

F(N)=exp(k*N^(2/3)) , где коэффициент k порядка единицы

Здравствуйте, kfmn, Вы писали:

K> Однако с ненулевой вероятностью он может накрыть только 2^d или (2^d-1) кубов — в остальных случаях центр шара пробегает многообразие размерности меньшей d (для примера — в двумерном случае круг накрывает 2 квадрата, когда его центр находится на кресте из отрезков параллельных сторонам и проходящих через центр квадрата).

Погорячился я, каюсь.

В двумерном-то случае рассуждение и ответ вроде правильные, а дальше мимо.

В трехмерном случае есть ненулевая вероятность накрыть и 5 и 6 кубиков, а не только 7 и 8. Вот меньше уже нет.

Так что буду думать дальше, а впредь стану осторожнее в высказываниях

MP>Есть большое подозрение, что формула следующая:
MP>

MP>d+1+(1-(d+1)/2^d)*V(d), где V(d)=pi^(d/2)/Г(1+d/2) - объем гиперсферы единичного радиуса, а Г - гамма ф-ция
MP>

MP>Таким образом:

MP>1 — 2
MP>2 — 3+pi/4
MP>3 — 4 + 2*pi/3

MP>Строго доказывать формулу и строить графики — нет времени (работа )
MP>

Придется, похоже объяснить происхождение формулы. Сразу оговорюсь, что излагаю тезисы и не рассматриваю области нулевого объема.

1. Можно ограничиться одним рассмотрением одного квадранта гиперкуба и центра гиперсферы в нем.
2. Если в гиперсфера "захватывает" вершину 2^d — пересечений.
3. При остальных положениях центра гиперсфера обязательно пересекает каждую грань плюс сам гиперкуб. Итого d+1
4. Рассматриваем объемы областей и получаем искомую формулу.

Здравствуйте, Pushkin, Вы писали:


P>Для N-мерного

P>F(N)=SUM[n=0-N]{C(N,n)*(1/2)^n*V(n)}

P>где V(n) — объём единичного n-мерного шара

P>V(n) = pi^(n/2) / (n/2)!

Или я не понял формулы, или в одномерном случае получается 3/4.

У меня

Автор: MichaelP
Дата: 27.02.03

, имхо, более правильное число — 2.
Если у меня что-то не так в доказательстве — опровергните пожалуйста!

P.S. Сейчас пришло в голову, что мое решение получается довольно естественно, если начать думать: как эту задачу можно смоделировать на компьютере?

Здравствуйте, MichaelP, Вы писали:

MP>Здравствуйте, Pushkin, Вы писали:

MP>
P>>Для N-мерного

P>>F(N)=SUM[n=0-N]{C(N,n)*(1/2)^n*V(n)}

P>>где V(n) — объём единичного n-мерного шара

P>>V(n) = pi^(n/2) / (n/2)!

MP>Или я не понял формулы, или в одномерном случае получается 3/4.

Нет, по моей формуле тоже двойка получается. Смотрим.

Объём n-мерного единичного шара у нас одинаково напиcан (я только написал Г(n/2+1) в виде (n/2)! )
Чтобы ни у кого не было вопросов, сразу напишу (1/2)!=sqrt(pi)/2 — чуть меньше 1 (0!=1!=1)
И для объёма одномерного шара получаем, разумеется V(1)=2

Объём 0-мерного шара представить трудно, но подставив 0 в формулу имеем V(0)=1
C(1,0) тоже странная запись конечно, но механическая подстановка тоже даёт 1.
Короче первый член в сумме равен всегда 1, я просто не стал его отдельно выделять.
Можно было бы записать F(N)=1+SUM[n=1-N]

Подставляем
F(1)=SUM[n=0-1]{C(1,n)*(1/2)^n*V(n)} = 1 + C(1,1) * (1/2)^1 * 2 = 1 + 1*1/2*2 = 2

MP>У меня

Автор: MichaelP
Дата: 27.02.03

, имхо, более правильное число — 2.
MP>Если у меня что-то не так в доказательстве — опровергните пожалуйста!

MP>2. Если в гиперсфера "захватывает" вершину 2^d — пересечений.
MP>3. При остальных положениях центра гиперсфера обязательно пересекает каждую грань плюс сам гиперкуб. Итого d+1

Может быть больше, чем d+1. Это видно уже для d=3.
Шар может ребро пересечь, и тем самым захватить лишний кубик.
У меня так формула и построена — перебор всех гиперрёбер на предмет пересечения с шаром.
Мне кажется, трёхмерный случай вполне хороший тест — у нас получаются разные ответы
У меня 4 + 11*pi/12
У тебя 4 + 2*pi/3

У меня больше, потому что я учитываю не только пересечения с 6 ближайшими соседями и 8 самыми дальними, но и с 12 "промежуточными" — у которых с нами общее ребро (а не грань или вершина). Всего-то соседей 26, правда?

Здравствуйте, Pushkin, Вы писали:


P>Для N-мерного

P>F(N)=SUM[n=0-N]{C(N,n)*(1/2)^n*V(n)}

P>где V(n) — объём единичного n-мерного шара

Отлично
Чтобы остальные могли оценить, предложу свою интерпретацию формулы:

1. Рассматриваем центр гиперсферы лежащим в одном из квадрантов гиперкуба (за единицу считаем радиус сферы). Остальные рассматривать не надо, т.к. все квадранты равнозначны.
2. Пусть координаты центра x1, x2, ... xn. Очевидно, что каждая из них распределена равномерно на отрезке [0, 1]
3. Выполнение каждого из условий xi^2 + xj^2 + ... + xk^2 < 1 "добавляет" нам пересечение еще с одним гиперкубом.
4. Вероятность, что сумма квадратов длины m будет меньше 1 равна (1/2)^m*V(m), а количество таких сочетаний C(N, m).
5. Учтем также исходный гиперкуб (n=0, в формуле Puskin-а). Суммируем и получаем вышеуказанную формулу.