!!§!! Вспомогательная страница к разделу
☞
((:algebra2:optimiz:distance:torri:tree ДЕРЕВО ШТЕЙНЕРА))
----
==Поведение сети Штейнера при вариации терминала==
===Три терминала==
Алгоритм нахождения точки Ферма-Торричелли для терминалов на плоскости
$$ 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 $.
{{ algebra2:optimiz:distance:torri:ft11.png?400 |}}
В случае, когда вершины треугольника обходятся против часовой стрелки (как на рисунке), имеем:
$$
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} $ изображено на рисунке[[Создан **Елизаветой Семёновой** в системе ((http://www.sagemath.org SAGE)).]]
{{ :algebra2:optimiz:distance:torri:tree:trajectory1.jpg?600 |}}
{{ algebra2:optimiz:distance:torri:tree:motions2.gif |}}
При попадании точки $ 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 $. По ((:algebra2:optimiz:distance:torri#geometricheskoe_reshenie теореме Фаньяно)), эта точка обеспечивает
$$ \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. ((http://arxiv.org/pdf/1505.03564v1.pdf arXiv:1505.03564))