Алгоритм нахождения точки Ферма-Торричелли для терминалов на плоскости $$ P_1=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3) $$ основан на построении вспомогательной точки $ Q_1 $. На отрезке $ P_1P_2 $ строится равносторонний треугольник. Таких треугольников можно построить два. Нас интересует тот, который имеет вершину в полуплоскости, не содержащей $ P_3 $.

В случае, когда вершины треугольника обходятся против часовой стрелки (как на рисунке), имеем: $$ Q_1=\left(\frac{1}{2}x_1+\frac{1}{2}x_2-\frac{\sqrt{3}}{2}y_1+\frac{\sqrt{3}}{2}y_2\, ,\ \frac{\sqrt{3}}{2}x_1-\frac{\sqrt{3}}{2}x_2+\frac{1}{2}y_1+\frac{1}{2}y_2 \right) \, . $$ Для некоторых дальнейших рассуждений, мне потребуется и альтернативный вариант — для почасовой нумерации: $$ \widehat{Q_1}=\left(\frac{1}{2}x_1+\frac{1}{2}x_2+\frac{\sqrt{3}}{2}y_1-\frac{\sqrt{3}}{2}y_2\, ,\ -\frac{\sqrt{3}}{2}x_1+\frac{\sqrt{3}}{2}x_2+\frac{1}{2}y_1+\frac{1}{2}y_2 \right) \, . $$

Теорема. При любом расположении точки $ P_3 $ на плоскости, таком, что треугольник $ P_1P_2P_3 $ обходится против часовой стрелки, и выполняется условие существования точки Ферма-Торричелли, последняя будет лежать на окружности $ \mathfrak C_1 $, описанной вокруг треугольника $ P_1P_2Q_1 $.

Четырехугольник $ P_1P_2P_3P_4 $ предполагается выпуклым, при нумерации его вершин — против часовой стрелки.

Окружность $ \mathfrak C_1 $ — из предыдущего пункта. Окружность $ \mathfrak C_3 $ является описанной вокруг треугольника $ Q_1P_4Q_3 $. Здесь точка $ Q_3 $ определяется по аналогии с точкой $ Q_1 $. Именно, треугольник $ Q_1P_4Q_3 $ — равносторонний и лежит относительно прямой $ Q_1P_4 $ в полуплоскости, не содержащей четырехугольник $ P_1P_2P_3P_4 $.

Теорема. При фиксировании координат терминалов $ P_1,P_2 $ и $ P_4 $, и варьировании координат терминала $ P_3 $, точка Штейнера $ S_1 $ из дерева в топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $ передвигается вдоль окружности $ \mathfrak C_1 $. В то же время точка Штейнера $ S_2 $ движется вдоль окружности $ \mathfrak C_3 $.

Пример. Для терминалов

$$ P_1=(5,8),P_2=(1,1),P_5=(10,7) $$ и $ P_3 $ перемещающегося к $ P_2 $ из стартового положения в точке $ (11,3) $, геометрическое место точек Штейнера для топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $ изображено на рисунке¹⁾

При попадании точки $ P_3 $ на прямую $ Q_3 P_1 $, точки $ S_1 $ и $ S_2 $ сливаются в одну точку $ I $ пересечения окружностей $ \mathfrak C_1 $, $ \mathfrak C_3 $ и диагонали $ P_2 P_4 $, или, эквивалентно, диагоналей четырехугольника $ P_1P_2P_3P_4 $. По теореме Фаньяно, эта точка обеспечивает $$ \min_{S\in \mathbb R^2} \sum_{j=1}^4 |P_jS| \, . $$ Дерево в топологии с двумя точками Штейнера вырождается в решение задачи Ферма-Торричелли с одной узловой точкой.

Uteshev A.Yu. Some Analytics for Steiner Minimal Tree Problem for Four Terminals. 2015. arXiv:1505.03564