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

[dgwuqtj]

Я с теорией чисел вообще плохо знаком, но по аналогии можно попробовать коэффициенты $(1{,}83929; 2{,}38298; 1)$. Это один из собственных векторов матрицы $3 \times 3$, полученной произведением всех 6 элементарных трансвекций $E + e_{ij}$ при $i \neq j$ в каком-то порядке.

-- 04.05.2025, 21:16 --

Или, как вариант, можно попробовать собственный вектор $(0{,}295598; 0{,}543689; 1)$ матрицы $\Bigl(\begin{smallmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{smallmatrix}\Bigr)$.

[B@R5uk]

Вот оптимальное решение задачи Таммеса для 12 точек (слева) — икосаэдр — и самое (предположительно) неоптимальное локально-оптимальное решение (справа) — шестиугольная антипризма:

А существует ли какие-нибудь другие локально-оптимальные решения для этих же 12 точек?

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

[B@R5uk]

Нарандомил таки! (И потом ещё парочку)

Используется синтаксис Text

Number of points:     12
Number of hard edges: 22
Minimal   distance:   0.946381744331735
Spherical distance:   56.4832462282324 deg
Coordinates:
   0.177290145704347   0.729774432367815   0.660301054139977
  -0.260639548037514   0.396237070495425  -0.880376743198050
  -0.301966518196539  -0.032070794229419   0.952778928212497
  -0.703211237313640  -0.626802005306090   0.335578905564821
   0.199358103199455   0.944491300490342  -0.261136994672869
  -0.062828887217139  -0.958795646052928  -0.277062159164699
   0.190491104528593  -0.765861293886776   0.614141366154040
   0.794041667683467  -0.600274692828135  -0.095750316618521
  -0.735521229001013  -0.362276068125074  -0.572507268209476
   0.763314412978075  -0.013196868492650   0.645892366886252
   0.329759702173601  -0.343402142388305  -0.879393829535721
   0.862402670471183   0.287378723506216  -0.416743450146622


Number of points:     12
Number of hard edges: 22
Minimal   distance:   0.944356346144913
Spherical distance:   56.3515592072473 deg
Coordinates:
   0.792828107819916  -0.575806171048887   0.199676851018618
   0.279884456402482   0.941705958241352  -0.186693811565957
  -0.754912287310938   0.129083035786601   0.642996896057114
   0.675760081029524   0.250085545521335  -0.693401422560026
  -0.264609273852678  -0.676820341388011   0.686946983161419
   0.422824313360127  -0.066706390250879   0.903753206097347
   0.041028288825196  -0.415130415376275  -0.908836298650972
  -0.225721209792173   0.488368961058214  -0.842938724537483
  -0.637137470248441   0.769669185824159  -0.040806720012679
  -0.029027996868475   0.731974726335908   0.680713137381142
   0.021613920139598  -0.987241478743329  -0.157756461372851
   0.907170150249136   0.361471147552754   0.215362317929241

Number of points:     12
Number of hard edges: 22
Minimal   distance:   0.944787588504551
Spherical distance:   56.3795908561295 deg
Coordinates:
   0.775162550491410   0.411842546429173   0.479070701740763
  -0.453187473452015  -0.136048733667709  -0.880972108510589
  -0.472794345831826  -0.659610458236908   0.584276946262603
  -0.968818840726522  -0.228931298017325  -0.094765577302207
   0.035086293872793   0.661907041199515  -0.748764329273754
   0.846580087832757   0.278574291579574  -0.453539986060789
  -0.714594523543634   0.677554199796843  -0.173997049570121
  -0.330366346435953  -0.887406641480916  -0.321508211089734
   0.410348347977647  -0.500526734294311  -0.762290772322929
  -0.697129667514467   0.254107000986279   0.670402758586902
   0.134966687079103  -0.060087413696073   0.989026539630868
  -0.037374077480997   0.892963910289894   0.448573999750573
 

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

-- 27.07.2025, 16:28 --

Интересно, так же, как много точек валентности ноль, может иметь произвольное локально-оптимальное решение? Например, существует 14-точечное решение с двумя точками валентности ноль. Оно представляет из себя шестиугольную антипризму на экваторе (правый рисунок в посте выше) с двумя 0-валентными точками на полюсах. Я подозреваю, что количество таких точек не может быть больше некоторой доли от общего числа точек. Но вопрос: как это всё взаимосвязано?

[B@R5uk]

Меня давно интересовал вопрос: а может ли быть так, что две или более точки валентности 0 находятся в локально-оптимальном решении рядом друг с другом. Наткнулся вот на реальный пример:

(КАРТИНКА)

Используется синтаксис Text

=============================================================
Number of points:     53
Number of hard edges: 98
Minimal   distance:   0.496991477821552
Spherical distance:   28.7770312145715 deg
Spherical distance:   0.502253943643456 rad
Distance cosine:      0.876499735486375
Coordinates:
  -0.069773549303067  -0.944041080776847   0.322363288268586
   0.114462344076251   0.796378865116726  -0.593867893545329
   0.732757584308091  -0.616028623525407   0.289093510194129
   0.490041553549772   0.044734992251378  -0.870550432923214
  -0.330347224100288   0.862923796238815  -0.382404541570868
   0.250928064315882   0.252449236672598   0.934507618718064
  -0.828035615943412   0.070871666047577  -0.556178231937259
   0.192309266610192  -0.240786193302249   0.951335458758299
  -0.952137822081338   0.279951757575066  -0.122721559608891
  -0.246046225493806   0.256578915247522   0.934680969727455
   0.053837611773995  -0.783916845455263  -0.618527195012429
  -0.651450931588156   0.758483497593332  -0.017733234660099
   0.421758578817734  -0.906145914862898   0.031926198817367
  -0.246159352008012  -0.463287525169210  -0.851334389321601
  -0.681694355825600   0.170671364429194   0.711452100003505
  -0.025071326858151  -0.984966057363481  -0.170918970308772
   0.844148415704052   0.505253102193042  -0.179256115624114
  -0.078634438479997  -0.620634340440579   0.780147191593243
  -0.456105651399919   0.092195094455675  -0.885137107638904
   0.890392174203090  -0.431598061054876  -0.144654380547449
  -0.969365305211705  -0.061779938007547   0.237727037401307
  -0.312507473264566   0.554215243936750  -0.771482042916052
  -0.701522848697380   0.542255658770952  -0.462411605916627
   0.726202953916255  -0.330641220546585  -0.602748416006853
  -0.830585020471606   0.449890751849488   0.328217664315139
   0.003482832025088  -0.059428611691934  -0.998226482314236
   0.839330203990202   0.146760531356321  -0.523436868309614
  -0.679113568542293  -0.399521993943707  -0.615781566285479
  -0.812821093931295  -0.555772805411675   0.174466208834747
  -0.355078452991410  -0.227498946295462   0.906732331868497
  -0.472892405247454   0.614521386924489   0.631455650122540
  -0.287397797916067   0.915346911918394   0.282032864387211
   0.485741488035821   0.585029726637229   0.649457793664466
   0.996924308096477   0.046889724436221  -0.062795522680009
   0.335881002856623  -0.766219607936977   0.547806046272706
   0.679609001027813   0.113857957040048   0.724684739276773
   0.601681959553426  -0.376566703373362   0.704397854524323
   0.635883609600089   0.744516747853394   0.203339241681895
   0.478952740484750   0.838857953113786  -0.258692108267525
  -0.415139745663247  -0.788331105248813  -0.454084859985268
  -0.939042729517751  -0.270385667424077  -0.212344868060162
   0.884228262960421   0.332474639875753   0.328025902668501
   0.910733515758231  -0.161048885651048   0.380299513154051
   0.144070965917106   0.407410990529446  -0.901809204641164
   0.511776503501911  -0.744178053549212  -0.429282931269186
   0.199511666981199   0.902858017260659   0.380844450407953
   0.549846850896114   0.532475735702561  -0.643535571237242
  -0.737256562729906  -0.310475698826399   0.600047999038363
   0.042037315032009   0.995804023714891  -0.081284749480658
   0.005653927980705   0.648451431029231   0.761235032492943
  -0.477050736995694  -0.722142417091458   0.500932055042569
   0.306538162506861  -0.425055135280064  -0.851682151332858
  -0.467723429793956  -0.883334599481513   0.030899491591510

 

[B@R5uk]

Евгений Машеров в сообщении #1681388 писал(а):

Ещё попытка в эмпирический алгоритм. Набрасываем точки случайно. Затем вычисляем расстояния между точками. Находим минимальное расстояние. Затем для каждой из двух точек, расстояние между которыми минимально, находим три ближайшие и строим окружности через них. Точку, для которой радиус окружности больше, перемещаем в центр окружности. Пересчитываем расстояния. И т.д. Условие остановки непонятно, возможно, будет зацикливание.

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

Евгений Машеров в сообщении #1681388 писал(а):

находим три ближайшие и строим окружности через них.

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

В процессе штудирования "Численной оптимизации" Носедаля допёр до неожиданно простого и красивого способа определения того, является ли точка (назовём её C — центр окружности) "зажатой" тремя равными по длине отрезками, выходящих из неё и заканчивающихся в трёх других точках. Демонстрационная картинка под катом:

(КАРТИНКА)

Ключевая идея заключается в том, чтобы рассмотреть задачу нахождения координат центра окружности:

$$\begin{cases}|R_C-R_1|^2=L^2\\|R_C-R_2|^2=L^2\\|R_C-R_3|^2=L^2\end{cases}$$

как оптимизационную задачу:

$$\begin{cases}R_C^*=\underset{R_C}{\arg\max}\,L\\|R_C-R_1|\ge L\\|R_C-R_2|\ge L\\|R_C-R_3|\ge L\end{cases}$$

Решение у этих двух задач одно и то же (когда второе решение ограничено), но в процессе решения второй задачи мы получим множители Лагранжа, которые будут нести дополнительную (и представляющую непосредственный интерес) информацию. А именно: если знаки множителей одинаковы, то центр окружности "распирается" отрезками, соединяющими его с остальными тремя точками и расстояние до них нельзя монотонно увеличить непрерывным движением. Если же центр окружности лежит "в стороне" от трёх других точек, то один из множителей Лагранжа окажется отличного от двух других знака. В этом случае расстояние от C до точек 1, 2 и 3 можно монотонно увеличивать. При этом ребро, соответствующее множителю Лагранжа с неправильным знаком можно выкинуть, потому что его длина всегда (в процессе увеличения длин рёбер) будет больше, чем двух других.

Формула для расчёта множителей Лагранжа получается такая (для квадратичных связей, без корня, в коде ниже сделано с корнем, различие только в численных значениях). Координаты центра окружности (со звездочками) берём из первой задачи (особенно для неограниченного случая), а множители рассчитываем по формуле для второй:

$$\begin{pmatrix}x^*-x_1&x^*-x_2&x^*-x_3\\y^*-y_1&y^*-y_2&y^*-y_3\\1&1&1\end{pmatrix}\begin{pmatrix}\lambda_1\\\lambda_2\\\lambda_3\end{pmatrix}=\begin{pmatrix}0\\0\\1\end{pmatrix}$$

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

Используется синтаксис Matlab M

clc
clear all

names_str = '123C';

coords = 2 * pi * rand (1, 3);
coords = [cos(coords) 0; sin(coords) 0];
clim_min = min (coords, [], 2);
clim_max = max (coords, [], 2);
clim_diff = max (clim_max - clim_min);
coords = 0.5 * [1; 1] + 0.9 * (coords - repmat (0.5 * (clim_min + clim_max), 1, 4)) / clim_diff;
disp ([char(10) 'coords ='])
disp (coords)

mat_diff = zeros (3, 3);
for k = 1 : 3
    coords_diff = coords (:, 4) - coords (:, k);
    coords_diff = coords_diff / sqrt (sum (coords_diff .^ 2));
    mat_diff (k, 1 : 2) = coords_diff;
end
mat_diff (:, end) = 1;

disp ([char(10) 'mat_diff ='])
disp (mat_diff)

mul_lagr = pinv (mat_diff') * [0 0 1]';

disp ([char(10) 'mul_lagr ='])
disp (mul_lagr)

clf reset
plot (coords (1, :), coords (2, :), 'o')
hold on
for k = 1 : 3
    xx = coords (1, [k 4]);
    yy = coords (2, [k 4]);
    plot (xx, yy, 'k')
end
hold off
xlim ([0, 1])
ylim ([0, 1])
axis equal
for k = 1 : 4
    text (0.03 + coords (1, k), coords (2, k), names_str (k), 'FontSize', 14)
end
title ({['\lambda_1 = ', num2str(mul_lagr (1), '% 6.4f')], ['\lambda_2 = ', num2str(mul_lagr (2), '% 6.4f')], ['\lambda_3 = ', num2str(mul_lagr (3), '% 6.4f')]}, 'HorizontalAlignment', 'Right')
set (gcf, 'GraphicsSmoothing', 'off')

 

А вообще, в общем случае поиска оптимального положения одной точки среди пачки других задачу можно решать через линейное программирование. Линеаризируем связи, оптимизируем смещение координат точки, применяем его к координатам, повторяем до победного. Сходимость (по моему опыту) будет (после "устаканивания" положения) квадратичной (удвоение числа значащих цифр решения за одну итерацию). Предложенный вами, Евгений Машеров, алгоритм, сходится будет гарантированно, если на каждой итерации выбирать самое короткое ребро и из двух возможных вариантов движения выбирать тот, который даст наибольшее увеличение длины. Доказательство просто: рост длины кратчайшего ребра монотонен и ограничен сверху. Даже сходимость, скорее всего, будет линейная (отклонение от решения убывает по экспоненте). Однако, вот, фигура, к которой точки будут сходится, будет вызывать вопросы: скорее всего это будет набор точек в положении, при котором какое-то число рёбер имеют одинаковую длину, являющуюся минимальной. Алгоритм это гарантирует, а вот того, что число таких рёбер будет максимально (конфигурация локально оптимальна) алгоритм не гарантирует. Как дешёвую с точки зрения трудоёмкости начальную затравку можно использовать.

-- 13.12.2025, 19:23 --

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