Равномерное распределение точек на сфере

[Griboks]

Любопытно, разве Монте-Карло не даёт идеального распределения при больших N?

[Soffort]

Ага. С определённой вероятностью, зависящей от величины N :)

[Phaker]

С нулевой вероятностью. Каковы шансы, случайно выбирая точки на отрезке [0, 1], заполнить его строго равномерно (все расстояния между соседними парами точек равны)? Шансов нет.

[Soffort]

Строго математически — шансы нулевые. Но если нам «ехать», т.е. для практических целей, то можно попробовать. Хоть и не нужно, если уже есть готовые алгоритмы.

[Griboks]

Почему с нулевой? Мы говорим про сферу, а не отрезок. Хотите узнать вероятность? Возьмите интеграл объёма границы (толщины) сферы.

[Griboks]

строго равномерно

Не заметил. Вероятность, согласно центральной предельной теореме, стремиться к 1. Ну а c вычислительной точки зрения, она равняется 1. Впрочем, я сгенерировал случайные точки, можете сами проверить.

[mayorovp]

Какое нафиг стремление к 1?

Посмотрите внимательнее чего именно пытаются добиться в этой статье. А пытаются добиться чтобы точки на сфере шли как можно более ровной сеткой.

Случайные же точки выглядит как-то так (взял первую попавшуюся картинку, можете попробовать нарисовать ваши точки — должно получиться что-то похожее):

Ну и где тут ровная сетка?

[Griboks]

Случайные же точки выглядит как-то так

Ну давайте проверим: берём отрезок от 0 до 1 и рассыпаем на него точки.
Количество точек / Среднее / Дисперсия / Отношение дисперсии к среднему
N=10^1 Mx=0.1057107049613101 Dx=0.014991353458562295 DMRx=0.14181490383636264
N=10^2 Mx=0.009925959274512302 Dx=0.00010322180977963227 DMRx=0.010399177240700892
N=10^3 Mx=0.0009988373664351917 Dx=1.0482468240416785e-06 DMRx=0.0010494669695656532
N=10^4 Mx=9.999876742558959e-05 Dx=9.68829614329053e-09 DMRx=9.6884155602215e-05
N=10^5 Mx=1.000006934144877e-05 Dx=9.968157388129179e-11 DMRx=9.968088267960981e-06
N=10^6 Mx=1.0000006018870852e-06 Dx=9.99976735903523e-13 DMRx=9.999761340308023e-07
N=10^7 Mx=9.999998466395956e-08 Dx=9.998199637750894e-15 DMRx=9.998201171079068e-08

Кокой вывод можно сделать? Генератор случайных чисел на компьютере не идеальный + точность == порядку N + отношение Dx/Mx уменьшается с ростом количества точек и стремиться к нулю. Следовательно, при большом количестве точек погрешность занимает больше 32 бит и обнуляется. Получаем абсолютно равномерное распределение.

[mayorovp]

Вот только если уж говорить про и правда большие N — то разрядность тоже должна стремиться к бесконечности (в том числе разрядность ГСЧ!). Иначе вся случайность вырождается в равномерную сетку из 2³² ячеек, а этот вариант никому не интересен.

[Griboks]

Однако количество разрядов погрешности растёт быстрее, поэтому можно ограничиться, например, 32 битами (а в общем случае условием задачи) и быть уверенными, что это равномерное распределение без дополнительных критериев. Или вы не согласны?

[amphasis]

Вам же объяснили, что это не то равномерное распределение которого пытаются добиться в статье. Вы говорите о равномерном распределении случайной величины. В статье говорится о минимизации разброса расстояний между соседними точками на сфере, что, предвещая ваш следующий комментарий, для краткости и удобства читателя назвали равномерным распределением точек на сфере.

[Griboks]

1. Я говорю о псевдонормальном распределении случайной величины расстояния между соседними точками (см. центральную предельную теорему).
2. В статье говорится о равномерном (но не статистическом; однородном, если хотите) распределении точек (см. заголовок и вступление).
3. В качестве меры равномерности предлагаются 4 критерия, 2 из которых рассматриваются на примерах.
4. Я показываю теоретически и проверяю практически, что методом Монте-Карло возможно равномерно распределить точки при большом их количестве.

Теперь, пожалуйста, объясните мне ещё раз, что вы пытались сказать, и почему этот ваш разброс расстояний между соседними точками в 9.9e-08 нельзя назвать удовлетворительным?

[amphasis]

А вы попробуйте посчитать не абсолютную величину разброса, а разброс относительно среднего расстояния между точками (причем не на отрезке, а хотя бы на плоскости).
Почитайте введение внимательнее, там довольно ясно описано к какому распределению стремятся.

[Griboks]

Хорошо, получается ~ 100%. Вы предлагаете брать не среднее расстояние, а минимальное? Ну хорошо, давайте возьмём:
N=10^1 Min=0.016212136413931155 Max=0.37461837137749365 Mean=0.09401552286663975
N=10^2 Min=1.9124122053626458e-05 Max=0.04580802524341976 Mean=0.01002876616106881
N=10^3 Min=5.292099047871091e-07 Max=0.00662962744940665 Mean=0.0010004000030152745
N=10^4 Min=3.842715812218955e-09 Max=0.0008187438221771703 Mean=0.00010000210209493355
N=10^5 Min=1.6746826148050786e-11 Max=0.00011494501323361384 Mean=9.999970245561979e-06
N=10^6 Min=6.814548925149211e-13 Max=1.3744202724041976e-05 Mean=9.999999409152049e-07
N=10^7 Min=3.4083846855992306e-14 Max=1.929901522923494e-06 Mean=1.0000000462518477e-07

Какой из этого мне надо сделать вывод?

[amphasis]

Хорошо, получается ~ 100%.
Какой из этого мне надо сделать вывод?

Наверное, что для решения поставленной в посте задачи метод Монте Карло на ~100% не подходит :)

[Griboks]

А у вас есть требуемое граничное значение dN для сферы моего радиуса и моего N, чтобы так говорить? Думаю, тут дело не в относительной погрешности, а в точности. В этом ведь и есть суть центральной предельной теоремы: количество перерастает в качество.

[mayorovp]

Почему вы так уверены, что количество разрядов погрешности растёт быстрее?

[Griboks]

Посчитал. У вас получились другие результаты?

[mayorovp]

Вы считали численно? А у использованного ГСЧ было сколько разрядов?

Вы постулировали что 32 разряда вам хватит — максимум, и получили в результате что 32 разряда вам хватит.

[Griboks]

Думаю, так получилось потому, что я заранее определил точность, как в реальной задаче. А может просто так сгенерировалось.

[Griboks]

Еще раз проверил. Вы были правы — растёт одинаково, вырождается в сетку. Однако, мы всё-равно можем изменять масштаб это сетки, пока она не будет казаться однородной.

[amphasis]

Но ведь в этом случае во-первых проще сразу взять нужную сетку, во-вторых при натягивании этой сетки на сферу все равно придется бороться с неоднородностями вызванными преобразованием координат.

[Griboks]

1. нужную сетку нужно как-то сгенерировать
2. речь идёт об изначально сферической сетке в 3d

[mayorovp]

Ах да, вот еще момент. Отношение дисперсии к матожиданию ничего не означает, это величины разных порядков. Надо смотреть на отношение стандартного отклонения к матожиданию.

[ialexander]

Там немного другая задача. Там пытаются равномерно распределить N точек на сфере. Есть разные критерии равномерности — например, минимальное расстояние между двумя точками. Таким образом, максимизируя минимальное расстояние между точками, мы располагаем точки по узлам сетки, с равным расстоянием между соседними узлами. Это оптимальное решение.

Предлагаемый в статье подход даёт приемлемое решение для любых N, в числе малых в районе 10.

Положим Монте-Карло может для больших N разместить точки близко к узлам равномерной сетки. Но Монте-Карло работает только для (очень) больших N. Его бессмысленно использовать даже для N в районе 1000.

[Griboks]

Спасибо за внятный ответ. Сразу становится понятно, почему его не упомянули.

[Gostra]

Удивительно что не упомянули одну из важнейших областей применения — расстановка взрывателей на поверхности 239Pu сферы для качественного биг-бара-бум.