Расположение точек на сфере

[B@R5uk]

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

Aritaborian, есть ещё один, более простой вариационный способ. В нём используется значительно больше варьируемых переменных, а оптимизируется минимальная длина группы ключевых рёбер (минимально необходимое число). Например, для фигуры с 11-ю точками варьируемыми являются четыре θ-координаты точек 1, 4, 9, 12(13), φ-координаты фиксированы, а оптимизации подвергается минимум из множества длин рёбер 1-4, 4-9, 9-12 и 12-13. Для такой схемы решения код писать значительно проще, так как функция fminsearch принимает любое количество переменных для оптимизации. Тут главное начальное приближение угадать.

-- 22.07.2018, 18:40 --

И всё-таки мне хотелось бы узнать что-нибудь по поводу моего вопроса:

B@R5uk в сообщении #1328195 писал(а):

...как в таких случаях доказывается, что другого, более лучшего решения нет?

[grizzly]

B@R5uk в сообщении #1328195 писал(а):

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

Да нет никакого универсального сценария. А какой ответ Вы ожидаете получить? Посмотрите для примера 67-страничное строгое доказательство (с помощью компьютера, конечно) задачи Томсона для 5 точек на сфере.

-- 22.07.2018, 19:53 --

B@R5uk
Кстати, таки да, квадратная антипризма -- лучшая из известных на сегодняшний день конфигураций для 8 точек (см. англовики).

[Munin]

Хм, а почему на торе никто точки не располагает? Разве это более простая задача?

[B@R5uk]

firstround в сообщении #1328203 писал(а):

В чем разница между "минимаксной задачей" и задачей Томпсона?

В целевой функции. В задаче Томпсона целевой функцией является потенциал Кулона для набора точек, который является всюду гладкой функцией (за исключением выколотых случаев совпадающих точек). Эта функция очень хороша для численной минимизации, поскольку изменение любой координаты любой точки приводит к изменению целевой функции (потенциала). В моей же задаче задаче целевой функцией является минимум набора расстояний между всеми парами точек. Эта функция непрерывна, но в отличие от задачи Томпсона, она является ломаной функцией, состоящей из кусков гиперплоскостей. Но самая паршивая особенность заключается в том, что значение функции на каждом участке гиперплоскости зависит только от координат двух точек (расстояние между которыми минимально) и не зависит от координат других точек. Численная минимизация такой функции сущий ад, а подходы "в лоб" просто не работают.

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

firstround в сообщении #1328203 писал(а):

Примерно такой крокодил и хочется получить. В чем проблема нахождения аналитического решения данной задачи?

Зачем тогда далеко ходить? Записать исходную систему, указать отрезок локализации и сказать, что это ответ.

-- 23.07.2018, 00:43 --

grizzly в сообщении #1328237 писал(а):

Да нет никакого универсального сценария.

Понятно.

grizzly в сообщении #1328237 писал(а):

Посмотрите для примера 67-страничное строгое доказательство

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

grizzly в сообщении #1328237 писал(а):

квадратная антипризма -- лучшая из известных на сегодняшний день конфигураций для 8 точек

Ну, я решал немного другую задачу. То, что в задаче Томпсона тоже получается такая фигура, — это удача.

-- 23.07.2018, 00:46 --

Munin в сообщении #1328273 писал(а):

Хм, а почему на торе никто точки не располагает? Разве это более простая задача?

Разве только если вы имеете в виду топологический тор с плоской метрикой в квадрате/прямоугольнике. Кстати, интересная постановка, надо будет поразмышлять над простыми случаями.

[Munin]

B@R5uk в сообщении #1328279 писал(а):

Разве только если вы имеете в виду топологический тор с плоской метрикой в квадрате/прямоугольнике.

Именно; он же вкладывается изометрически в 4-мерное евклидово пространство, как поверхность, заданная уравнениями

$$\begin{cases}x_1^2+x_2^2=r^2\\x_3^2+x_4^2=r^2.\end{cases}$$

[grizzly]

Munin в сообщении #1328273 писал(а):

Хм, а почему на торе никто точки не располагает?

Статьи по задаче Томсона на торе гуглятся. Вот здесь с картинками при большом количестве точек. Саму эту ссылку нашёл здесь. А внутри там ещё такая есть. (В содержание не вникал.)

[B@R5uk]

Munin в сообщении #1328282 писал(а):

Именно; он же вкладывается изометрически в 4-мерное евклидово пространство

Нет, я имел в виду именно плоский квадрат, у которого сшиты противоположные стороны. Или вы имеете в виду, что эти две фигуры топологически эквивалентны?

[Someone]

B@R5uk в сообщении #1328286 писал(а):

Или вы имеете в виду, что эти две фигуры топологически эквивалентны?

Там же написано:

Munin в сообщении #1328282 писал(а):

вкладывается изометрически

Изометрически — это с сохранением расстояний между точками.

[Munin]

B@R5uk в сообщении #1328286 писал(а):

Нет, я имел в виду именно плоский квадрат, у которого сшиты противоположные стороны. Или вы имеете в виду, что эти две фигуры топологически эквивалентны?

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

$$\begin{cases}x_1^2+x_2^2=r^2\\x_3^2+x_4^2=r^2.\end{cases}$$

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

Однако, если измерять расстояния "через пространство", то конечно, метрика на торе, вложенном в 4-пространство, другая, чем на плоском квадрате.

[Someone]

Ну так если склеить тор из квадрата, на торе в любом случае метрика будет другая, нежели на квадрате.

[Munin]

Да, "вкладывается изометрически" принято понимать (насколько я в курсе) именно в смысле "внутренних" расстояний.

[B@R5uk]

Someone, спасибо за разъяснение. Я не со всеми терминами знаком.

Munin, для двух и для четырёх точек решение вроде бы очевидно: вершина квадрата и центр квадрата в первом случае и квадрат вдвое меньшего размера во втором (с параллельными исходному сторонами). Кстати, ко мне тут пришло понимание, почему такая постановка задачи хуже, чем сферическая. Количество и тип симметрий получающегося распределения точек будет жёстко привязано к симметриям квадрата. На сфере получившуюся фигуру можно свободно вращать, в то время как в квадрате такое не взлетит. Поэтому в квадрате, например, будут отсутствовать симметрии поворота на 120 градусов. Хотя, некоторое утешение в связи с этим недостатком могут стать трансляционные симметрии со смешением на треть размера стороны квадрата. Но всё равно, сфера в этом плане многогранней.

-- 23.07.2018, 01:20 --

Решение с тремя точками в квадрате тоже вроде очевидно: одна точка находится в вершинах квадрата, а прямая проходящая через две другие делит квадрат на две равные части, проходя через центры противоположных сторон. Ну и равные расстояния между точками. Самое интересное, видимо, начинается с пяти точек.

[Munin]

Someone
Уф. Не путайте меня.

На квадрате $(\varphi_1,\varphi_2)\in[0,2\pi]\times[0,2\pi]$ евклидова метрика такая:

$$\rho(\Delta\varphi_1,\Delta\varphi_2)=\sqrt{\smash[b]{\Delta\varphi_1^2+\Delta\varphi_2^2}}.$$

На квадрате со склеенными сторонами такая:

$$\rho(\Delta\varphi_1,\Delta\varphi_2)=\sqrt{\smash[b]{\min\{\Delta\varphi_1,2\pi-\Delta\varphi_1\}^2+\min\{\Delta\varphi_2,2\pi-\Delta\varphi_2\}^2}}.$$

Когда мы вкладываем его в $\mathbb{R}^4,$ например,

$$x_1=1\cdot\cos\varphi_1,\quad x_2=1\cdot\sin\varphi_1,\quad x_3=1\cdot\cos\varphi_2,\quad x_4=1\cdot\sin\varphi_2,$$

то "внутренняя" метрика остаётся такой же (например, метрический тензор совпадает первой квадратичной формой), однако можно использовать и "внешнюю" метрику

$$\rho(\Delta\varphi_1,\Delta\varphi_2)=\sqrt{\smash[b]{\Delta x_1^2+\Delta x_2^2+\Delta x_3^2+\Delta x_4^2}}.$$

-- 23.07.2018 01:29:55 --

B@R5uk в сообщении #1328291 писал(а):

Munin, для двух и для четырёх точек решение вроде бы очевидно: вершина квадрата и центр квадрата в первом случае и квадрат вдвое меньшего размера во втором (с параллельными исходному сторонами).

А для 4 точек точно не параллелограмм?

[B@R5uk]

Придумал решение для пяти точек в "торическом" квадрате: одна точка как всегда в вершинах квадрата, а четыре других образуют квадрат меньшего размера, центрированный и повёрнутый относительно исходного. Двумя варьируемыми переменными являются ширина стороны и угол поворота малого квадрата. При этом надо удовлетворить двум равенствам: расстояние между ближайшими парами вершин малого и большого квадратов равна стороне малого квадрата и удвоенное расстояние от центра стороны большого до ближайшей вершины малого так же равна стороне малого квадрата.

-- 23.07.2018, 01:39 --

Munin в сообщении #1328292 писал(а):

А для 4 точек точно не параллелограмм?

Теперь я начал сомневаться с своём решении. Если сдвинуть две вершины малого квадрата на половину его ребра, то как минимум два расстояния точно увеличатся. Теперь бы как эту фигуру трансформировать так, чтобы увеличит другие два расстояния и уровнять с первыми двумя?

[Someone]

Munin в сообщении #1328292 писал(а):

Уф. Не путайте меня.

Да, точно, там же изометрия в смысле внутренней метрики.