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

[unistudent]

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

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

Не совсем так. Если множество узлов дополнить узлом в центре диска, то при $m=1$ будет три узла, лежащих на одной линии.

[arseniiv]

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

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

Да, тут самое страшное в выражении минимизируемой величины $a$ через число оболочек $L$ и количества вершин и углы поворота многоугольников. А если его получить, зафиксировать число оболочек и найти минимум $\min\limits_\text{остальные параметры} a(L)$, и так для каждого числа, то можно будет заметить, когда $\min\limits_\text{о. п.} a(L)$ после очередного $L = L_0$ перестанет уменьшаться и начнёт увеличиваться (это гипотеза. Может, там и несколько локальных минимумов будет — но как будто не должно), можно дальше не считать и сказать, что $\min\limits_L\min\limits_\text{о. п.} a(L) = \min\limits_\text{о. п.} a(L_0)$. А если попытаться оценивать $\min\limits_\text{о. п.} a(L)$, не считая явно $a$ для всех вариантов с фиксированным $L$, то, может, ещё меньше считать надо будет. Утопично получается, потому что явное выражение ни для СКО площадей областей диаграммы Вороного, ни для вашей исходной величины, по идее, должно быть довольно сложным. Но тут главное начать, и будет понятнее, что можно сделать — а пока это общие слова.

[denny]

мат-ламер
grizzly
Ваше совместное предложение - хорошая альтернатива.
Запишем его формально, чтобы всё было понятно.
Пусть $c$ - единичная окружность, $Set$ - набор из $N$ точек, $SuperSet = c \cup Set$, т.е. множество,
куда окружность включена наравне с точками.
Т.к. нас интересуют только попарные расстояния между элементами $SuperSet$, такой подход корректен.
Назовём степенью равномерности этого набора (версия 2) величину

$$\min(\underset{obj_1, obj_2 \in SuperSet}{dist(obj_1, obj_2)})$$

И действительно, процесс максимизации этой величины в Mathematica сходится, но...
Каждый раз к новым конфигурациям. Вообще "Constrained Optimization" -
довольно сложный раздел в Mathematica; там много опций. Наверное, я не все грамотно использую.
Дело еще в том, что функция слишком плоская - существуют целые области, где её значения одинаковы.
Поэтому использовал именно сами расстояния, а не квадраты; так хоть немного экстремумы острее.

Сделал вот такую игрушку на GeoGebra.

http://tube.geogebra.org/material/show/id/424961

Можно выбрать число точек и "ловить" максимум, двигая их.
Красное значение - лучшее, что было достигнуто; синее - текущее.
Там же и Вороной есть, но в GeoGebra его никак нельзя анализировать.

Для трёх точек мне удалось получить $0.6274$, а Mathematica нашла $0.6335 $

Конфигурации, найденные с помощью версии 2, отличаются от найденных по версии 1 (начало поста).
Поэтому можно сказать, что на вопрос №1 есть уже два ответа - оценка равномерности разбиения Вороного (но об этом позже),
и максимин расстояний точек и окружности.

Но неформальное размышление и игра с апплетом наводит на мысль,
что версия 2 оптимизирует равномерность относительного положения точек и окружности,
а не распределение точек по "сплошному" диску.
Ну вот просто посмотрите на версии 1 и 2 для трёх точек.
Имхо первая "равномернее", хотя это чистый субъективизм.



Всё же признавая удачным предложение мат-ламер и grizzly, продолжаю исследования.
На очереди Вороной и упаковка окружностей.

[grizzly]

У Вас же окружность является неучтённой точкой, так уж поделите расстояние к ней на 2, пжл (надеюсь, подробнее не нужно). Хотелось бы справа увидеть такую же картинку, какой уж там субъективизм.

-- 23.12.2014, 19:42 --

Ну, совсем такая же не получится -- вес (площадь) центральных точек не так значителен, как вблизи границы круга. Но, подозреваю, что субъективно будет даже лучше :)

[denny]

Цитата:

так уж поделите расстояние к ней на 2, пжл (надеюсь, подробнее не нужно).

Нужно...
Тем более, что если делить - они еще больше к центру сожмутся.
А вот когда умножил на 2, получилась конфигурация, неотличимая от версии 1.
И всё таки, мне кажется, это как-то искусственно...

[grizzly]

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

А вот когда умножил на 2, получилась конфигурация, неотличимая от версии 1.

Ну, значит, мы в разных частях равенства двойку ставили. Хорошо, что получили правильную картинку. Но почему совсем неотличимую? Немного странно.

Теперь объяснение. Вы отмечаете 3 точки в круге. Получили попарное расстояние между этими точками некоторое $D$. Когда Вы рассматриваете произвольную точку, то Вас интересует расстояние до ближайшей из избранных. Грубо говоря, это расстояние ожидаете не больше $D/2$. А с окружностью что получается? Вы берёте произвольную точку между избранной и окружностью, и смотрите куда будет ближе. Но ведь окружность не входит в число избранных. И получается зияющий провал.

Нет, как раз тут ничего искусственного.

[upgrade]

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

Имхо первая "равномернее", хотя это чистый субъективизм.

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

[denny]

Да, всё понял!
Работа с версией 2 очень затрудняется её слабой сходимостью.
Если считать моим методом, то нужно задавать большую решётку на диске
(на 2 порядка больше, чем размер конфигурации).
С параметрами также приходится играть. И считает долго.
Но уж когда посчитает, сразу видно - это не случайно. "Добротно, надёжно...".
Глобальный экстремум, короче.

А версия 2 ведь считается без решётки, по самой себе. Быстро, но в 99% сходится
к локальным экстремумам, коих бесконечное множество.
Для нескольких точек проще в GeoGebra играться, чем десятки попыток в Mathematica делать.

Нужен мощный метод оптимизации поиска экстремума по версии 2.
Тогда можно будет детально всё сравнивать.

-- 23.12.2014, 21:14 --

upgrade в сообщении #951286 писал(а):

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

Конечно, первые 3-4 точки являются центрами масс секторов "стола". А вот насчёт нормалей пока не понял...

[unistudent]

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

[upgrade]

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

Конечно, первые 3-4 точки являются центрами масс секторов "стола".

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

-- 23.12.2014, 20:31 --

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