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

[denny]

Приветствие участникам форума!

Хотел бы услышать ваше мнение об одной идее/гипотезе.

Началось всё с того, что моя знакомая спросила:
"Как можно красиво расположить точки на сфере?"
Слово "красиво", конечно, меня мало воодушевило.
В результате мы сошлись на множествах вершин платоновых и архимедовых тел.

Следующий вопрос пришёл нам обоим:
"А как наиболее равномерно распределить N точек на единичной сфере?"
Эта тема оказалась весьма нетривиальной; в целом изучена:
https://www.maths.unsw.edu.au/about/distributing-points-sphere
( плюс множество дискуссий на math.stackexchange),
но не имеет однозначного решения.

Возник очевидный вопрос: может, с единичным диском всё будет проще?
Какое распределение N точек внутри него можно считать равномерным?
(для любых N: малых (2, 3, 17,...) и сколь угодно больших). И по какому критерию?

Нашлись два любопытных подхода:
рассеивание по неким "спиралям золотого сечения"
http://blog.marmakoide.org/?p=1
(явно не то для небольшого числа точек)

и метод равных ячеек Isocell (возможен только для особых N)
http://orbi.ulg.ac.be/bitstream/2268/91953/1/masset_isocell_orbi.pdf

Иллюстрации на Геогебре:

http://tube.geogebra.org/student/m286063
http://tube.geogebra.org/student/m286087

Мне оба метода показались неудовлетворительными.
Предлагается следующий критерий (для алгоритма оптимизации)
равномерности распределения конфигурации из N точек на единичном диске.

Поиск минимума среднего (по всем точкам диска) квадрата расстояния до конфигурации.

$\underset{p\in U}{Mean} (d^2(p,Set))\rightarrow \min$

Вопрос 1: существуют ли принципиально иные, осмысленные и вычислимые,
критерии равномерности?

Перепробовал множество подходов - различные комбинации max и min,
разные метрики для расстояния; но они давали вырожденные результаты:
все точки в центре, все на единичной окружности и т.п.

Численная оптимизация на Mathematica при небольших N дала очевидные
(это и хорошо!) результаты (N=2, 3, 4, 7, 11, 21):



При большем числе точек наблюдается некая хаотичность; но целевая функция всё равно
меньше, чем у конфигураций, полученных с помощью спиралей и Isocell (N=36):



И тут мне пришла идея: а что, если оптимальная конфигурация -
это набор из нескольких правильных многоугольников, концентрично расположенных
вокруг центра?
Тогда можно проводить оптимизацию не по координатам, а по радиусам и относительным углам поворота.
Количество точек в каждом многоугольнике также подлежит уточнению.
Ниже приведён пример для N=36;
видно, что по симметричности он не уступает конфигурации Isocell, но целевая функция меньше.



Вопрос 2: Наличие правильных многоугольников заставляет предположить, что всю конфигурацию можно найти неким точным, аналитическим или геометрическим, методом.
Как можно к нему подступиться?

[arseniiv]

denny в сообщении #950582 писал(а):

Вопрос 1: существуют ли принципиально иные, осмысленные и вычислимые,
критерии равномерности?

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

denny в сообщении #950582 писал(а):

Вопрос 2: Наличие правильных многоугольников заставляет предположить, что всю конфигурацию можно найти неким точным, аналитическим или геометрическим, методом.
Как можно к нему подступиться?

Если ничего не придумается, можно попробовать просто переписать способ оптимизации формулами и попробовать что-то оттуда вывести. И, может быть, есть смысл сначала посчитать количество «оболочек», на котором достигнется минимум, а потом остальные параметры.

(Оффтоп)

denny в сообщении #950582 писал(а):

Возник очевидный вопрос: может, с единичным диском всё будет проще?

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

Кстати, не пробовали определять «плохие» количества точек (например, укладывающиеся не настолько плотно, как в среднем по соседям)?

[unistudent]

Решетка $\{(x_{k,j}, y_{k,j}),0\leq k < 2m, 0 \leq j < m\}$, $x_{j,k}=\cos\frac{\pi j}{2m}\cos\frac{(2k+j)\pi}{2m}$, $y_{j,k}=\cos\frac{\pi j}{2m}\sin\frac{(2k+j)\pi}{2m}$, разбивает единичный диск на ромбы со стороной $d=2\sin\frac{\pi}{2m}$. При этом, чем ближе к центру диска расположен ромб, тем более он вытянут в радиальном направлении; наоборот, ромбы, расположенные ближе к границе диска, более вытянуты вдоль касательных к границе. Не знаю как насчет равномерности, но в задачах интерполяции на диске эта решетка бывает весьма удобной. На картинке решетка при $m=4$

[denny]

Спасибо, не ожидал такой заинтересованности!

unistudent, вам мне будет проще ответить. В течение 1-2 часов
проверю (на 2-3 примерах) значение оптимизируемой функции для модели ромбов.
Но, интуитивно, ставлю на то, что:
- ромбы будут лучше спиралей по равномерности
- возможно, лучше или почти одинаково с Isocell
- скорее всего, менее равномерны, чем модель автора.

[upgrade]

(Оффтоп)

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

[denny]

upgrade
Да, хорошая идея. А существует непрерывное (конформное?) преобразование
круга в квадрат? Я не очень силён в этом.

Если есть явные фомулы - можно посмотреть.

[unistudent]

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

[мат-ламер]

denny в сообщении #950582 писал(а):

Перепробовал множество подходов - различные комбинации max и min,
разные метрики для расстояния; но они давали вырожденные результаты:
все точки в центре, все на единичной окружности и т.п.

Максимизировать минимум расстояний между двумя точками. Поскольку есть большая вероятность попасть в локальный максимум, который не является глобальным, то процедуру повторять многократно с различными начальными данными.

[electric_retard]

Неск. лет назад интересовался на тему точек равномерно распределенных на сфере.
Решение — формулы 9-11 и текст перед ними.

[grizzly]

мат-ламер в сообщении #950851 писал(а):

Максимизировать минимум расстояний между двумя точками.

Только этого мало -- нужно ещё как-то нетривиально учитывать расстояние до границы круга.
UPD: впрочем, что здесь нетривиального? считать расстояние до окружности наравне с (неучитываемой) точкой.

electric_retard
Здесь, похоже, равномерное распределение означает не совсем то же.

denny
Не могли бы Вы найти здесь (в разделе "круги в круге") заполнение на 21? Попробуйте запустить шевеление своего алгоритма, начиная с той начальной позиции (точки, понятно, в центрах кружков). Я думаю, что так Вы найдёте "равномерность" лучше, чем на Вашем рисунке выше. "Упаковка" -- не совсем та же задача, но при увеличении количества точек результаты будут асимптотически сходиться с Вашими желаниями (если я их правильно интерпретирую). На квадратах, например, это будет совсем не прямоугольная решётка.

[denny]

Для unistudent и, отчасти, electric_retard

Если искать большие решётки, дающие достаточно равномерное распределение,
то и ромбы, и спирали, и корректный рандом (как описано в mathworld)
дадут хорошее приближение.

Авторы Isocell в этом плане провели специальное исследование. Они оценивали
площадь случайно выбранной окружности внутри диска по числу точек конфигурации,
которые в неё попадают. И показали, что их метод стабильнее и точнее, чем конкуренты -
Монте-Карло, гексагоны и т.п.

Меня же интересует равномерность с самого начала, буквально с $N=2$.
В это случае, в частности, две точки должны быть центрами масс полудисков.
Это выполняется в случае Isocell, и у моего метода.
В методе ромбов точки лежат на граничной окружности, что уже не равномерно

[grizzly]

denny в сообщении #950880 писал(а):

Меня же интересует равномерность с самого начала, буквально с $N=2$

Вот-вот, посмотрите пакоманию :)
Где-то раньше они описывали свои алгоритмы. Я думаю, что Вам нужны почти такие, только Ваша задача будет много проще -- Вы не будете ограничены неупругостью и недеформированностью Ваших кружков.

[denny]

grizzly

О да, Пакомания - это очень увлекательно, спасибо!
Я думал об этом. Очень похоже, правда.

Да, на квадратах равномерность - это точно не прямоугольная рещётка.
Хотя доказать не могу.

С пакомании скачал координаты, но ещё не успел проверить.

-- 22.12.2014, 22:53 --

Deggial

Исправил

[ex-math]

denny в сообщении #950848 писал(а):

А существует непрерывное (конформное?) преобразование
круга в квадрат?

Конформное отображение существует. Гуглите интеграл Кристоффеля-Шварца.

[denny]

Для arseniiv

Диаграммы Вороного пришли сразу на ум. Но в Mathematica
они реализованы как-то туго. Например, общая граница может быть только
кусочно-линейной. Это значит, окружность придётся аппроксимировать 256-угольником...
Но в эту сторону надо продвинуться, спасибо за совет!
Ведь равномерность в том смысле, как предполагает алгоритм,
можно определить почти для любого множества, уж тем более для многоугольника.

Цитата:

И, может быть, есть смысл сначала посчитать количество «оболочек», на котором достигнется минимум, а потом остальные параметры.

Вот в этом самая интрига. Распределение точек по многоугольникам мне напомнило
электронные оболочки из таблицы Менделеева. Но никаких глобальных идей, как
из $N$ получить число оболочек, и количества точек на каждой - нет...