Как найти точку ферма

1. ^ Cut The Knot — The Fermat Point and Generalizations
2. ^ Entry X(13) in the Encyclopedia of Triangle Centers Archived April 19, 2012, at the Wayback Machine
3. ^ Entry X(14) in the Encyclopedia of Triangle Centers Archived April 19, 2012, at the Wayback Machine
4. ^ Entry X(15) in the Encyclopedia of Triangle Centers Archived April 19, 2012, at the Wayback Machine
5. ^ Entry X(16) in the Encyclopedia of Triangle Centers Archived April 19, 2012, at the Wayback Machine
6. ^ Kimberling, Clark. «Encyclopedia of Triangle Centers».
7. ^ Christopher J. Bradley and Geoff C. Smith, «The locations of triangle centers», Forum Geometricorum 6 (2006), 57—70. http://forumgeom.fau.edu/FG2006volume6/FG200607index.html
8. ^ Weisstein, Eric W. «Fermat Points». MathWorld.

Содержание

Задача. Пусть заданы координаты $ K_{} $ точек пространства $ mathbb R^{n}_{} $ : $ {P_j=(x_{j1},dots,x_{jn})}_{j=1}^K $. Определить координаты точки
$ P_{ast}=(x_{ast 1},dots,x_{ast n}) $, решающей задачу оптимизации:
$$
min_{Pin mathbb R^n} F(P) qquad npu qquad F(P)= sum_{j=1}^Km_j |PP_j| .
$$
Здесь $ | cdot | $ означает евклидово расстояние: $ |P_1P_2|=sqrt{(x_{11}-x_{21})^2+dots+(x_{1n}-x_{2n})^2} $, а величины $ { m_j }_{j=1}^K $ обычно (и практически везде в настоящем разделе) считаются положительными и называются весами.

Задача известна под различными названиями: обобщенная задача Ферма-Торричелли, задача Ферма-Торричелли-Штейнера,
задача Вебера, задача о взвешенной геометрической медиане.

Будем говорить о наборе
$$
left{
begin{array}{l|c|l} P_1 & dots & P_K \
m_1 & dots & m_K
end{array}
right}
$$
как о конфигурации весов.

Рассмотрим сначала плоский вариант задачи: пусть $ n=2_{} $, $ {P_j=(x_{j},y_j)}_{j=1}^K $,
$$
F(x,y)= sum_{j=1}^{K} m_j sqrt{(x-x_j)^2+(y-y_j)^2} .
$$

В этом случае поставленная задача называется задачей об оптимальном расположении (узловой) станции¹⁾, или — в случае $ K=3 $ — задачей о трёх заводах.

П

Пример. В городах $ P_{1},P_2,P_3 $ расположены источники полезных ископаемых: железной руды, угля и воды соответственно. Известно, что для производства одной тонны стали необходимо иметь $ m_{1} $ тонн руды, $ m_2 $ тонн угля и $ m_3 $ тонн воды. В предположении, что стоимость перевозки одной тонны груза не зависит от его природы, где следует расположить сталелитейное производство так, чтобы минимизировать транспортные издержки?

С конца XIX века подобные задачи стали предметом изучения в экономической географии. Систематические исследования были начаты Вильгельмом Лаунхардтом²⁾[6] и позднее развиты Альфредом Вебером³⁾[1] . Последний ввел понятие штандорта⁴⁾ — оптимального места размещения производства, «склада».

Каков должен быть первый общий подход к отысканию таких пунктов? С угловыми вершинами штандортной фигуры штандорт связан линиями — их Вебер называет «компонентами»,— по которым и происходит передвижение соответствующих тяжестей. Положим, что мы имеем перед собой производство, работающее с двумя локализованными материалами, причем на выработку $ 1_{} $ тонны продукта требуется $ 3/4 $ тонны одного материала и $ 1/2 $ тонны другого. В таком случае мы получаем штандортную фигуру, на «материаль­ных компонентах» которой передвигаются веса в $ 3/4 $ и $ 1/2 $, в то время как «потребительская компонента» отягощена $ 1_{} $.

В XX веке эти задачи выделились в подраздел теории исследования операций, известный в настоящее время как facility location problem или location theory (location analysis).

Частный случай задачи при $ n=2 , K=3 $ и $ m_1=m_2=m_3=1 $ известен как (классическая) задача Ферма-Торричелли: для трех неколлинеарных точек плоскости
$ P_1=(x_1,y_1), P_2= (x_2,y_2) $ и $ P_3= (x_3,y_3) $ требуется определить
$$
min_{(x,y)} F(x,y) quad npu quad F(x,y)= sum_{j=1}^3 sqrt{(x-x_j)^2+(y-y_j)^2} .
$$

Datis tribus punctis, quartum reperire, a quo si ducantur tres rectæ ad data puncta, summa trium harum rectarum sit minima quantitas

(лат.) Для трех заданных точек найти четвертую, такую что если от нее провести прямые линии до данных точек, сумма расстояний будет наименьшей) P. de Fermat, «Œuvres de Fermat», 1679, Livre I, Paris.

Рассмотрим теперь различные подходы к решению общей задачи. Для определения координат стационарной точки $ P_{ast}=(x_{ast},y_{ast}) $ составим градиентную систему уравнений:
$$
left{ begin{array}{lll}
displaystyle frac{partial F}{partial x} &= displaystyle frac{m_1(x-x_1)}{sqrt{(x-x_1)^{2}+(y-y_1)^2}}+dots+ frac{m_K(x-x_K)}{sqrt{(x-x_K)^2+(y-y_K)^2}} & = 0 \
displaystyle frac{partial F}{partial y} &= displaystyle frac{m_1(y-y_1)}{sqrt{(x-x_1)^2+(y-y_1)^2}}+dots+ frac{m_K(y-y_K)}{sqrt{(x-x_K)^2+(y-y_K)^2}} & = 0
end{array}
right.
$$
Система эта нелинейная и даже неалгебраическая относительно $ x_{} $ и $ y_{} $, поэтому уже проблема установления существования (и количества) ее вещественных решений решается специально разработанными под нее методами.

Если обозначить
$$
frac{x-x_j}{sqrt{(x-x_j)^{2}+(y-y_j)^2}} = cos gamma_j, frac{y-y_j}{sqrt{(x-x_j)^{2}+(y-y_1)^2}} = sin gamma_j ,
$$
где $ gamma_j $ означает угол, образованный вектором $ overrightarrow{PP_{j}} $ с осью абсцисс, то уравнения градиентной системы можно переписать в виде:
$$
left{ begin{array}{ll}
m_1cos gamma_1 + m_2 cos gamma_2 + dots + m_Kcos gamma_K &=0,\
m_1sin gamma_1 + m_2 sin gamma_2 + dots + m_K sin gamma_K &=0 .
end{array} right.
$$
Если под $ m_{j} $ понимать величину силы, приложенной в точке $ P_{} $, и направленной к $ P_{j} $,
то приведенные уравнения означают, что суммы проекций этих сил на координатные оси равны нулю, т.е. в точке $ P_{ast} $ силы должны уравновешиваться. Это обстоятельство используют для экспериментального определения точки $ P_{ast} $. На плоской доске, располагаемой горизонтально к поверхности Земли, рисуют многоугольник, подобный многоугольнику $ P_1 P_2 ldots P_K $ и просверливают в его вершинах отверстия, через которые опускают нити, связанные одним узлом. Если к свободным концам этих нитей подвесить грузы массами, пропорциональными $ m_{j} $, то при равновесии этой системы общий узел нитей будет находиться в искомой точке $ P_{ast} $.

Интуитивно понятно также, что если вес $ m_{i} $, приложенный сквозь отверстие $ P_{i} $, окажется много большим оставшихся весов, то узел затянется именно в это отверстие. Оказывается при возрастании $ m_{i} $ такое затягивание произойдет раньше выполнения условия $ m_i = displaystyle sum_{jne i} m_j $. См.

☟

НИЖЕ.

Известно для случая $ K=3 $ точек на плоскости для произвольных значений весов $ { m_j } $ и для случая $ K=4 $ точек в случае одинаковых весов.

Исторически самое первое из известных решений задачи было предложено Торричелли в период до 1640 г.⁵⁾. для случая $ K=3 $ точек и одинаковых весов $ m_1=m_2=m_3=1 $ (классическая задача Ферма-Торричелли). Алгоритм предлагал нахождение точки $ P_{ast} $ в идеологии классической геометрии: circinus et regula⁶⁾. На сторонах треугольника $ P_1P_2P_{3} $, как на основаниях, строятся новые треугольники — равносторонние; эти треугольники должны располагаться с внешней стороны треугольника $ P_1P_2P_{3} $. Для каждого треугольника строится описывающая его окружность. Пересечение этих трех окружностей и дает точку $ P_{ast} $. На рисунке показано нахождение точки $ P_{ast} $ для случая $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $.
С той поры было придумано много вариантов построения точки $ P_{ast} $. Так, к примеру, в этой же точке $ P_{ast} $ пересекаются прямые $ T_1 P_2 $ и $ T_2 P_1 $, и, вдобавок,
$$ |T_1P_2|=|T_2P_1|=|P_{ast} P_1|+|P_{ast} P_2|+|P_{ast} P_3| = min_{Pin mathbb R^2} sum_{j=1}^3 |PP_j| . $$

Это решение обобщается в [2,6] на случай различных весов. Рассмотрим систему уравнений из предыдущего пункта:
$$
left{ begin{array}{ll}
m_1cos gamma_1 + m_2 cos gamma_2 + m_3cos gamma_3 &=0,\
m_1sin gamma_1 + m_2 sin gamma_2 + m_3 sin gamma_3&=0 .
end{array} right.
$$
Из этих уравнений выразим $ cos gamma_1 $ и $ sin gamma_1 $ и подставим в равенство
$$
1=cos^2 gamma_1+ sin^2 gamma_1 =
$$
$$
=left(frac{m_2}{m_1} cos gamma_2 + frac{m_3}{m_1} cos gamma_3 right)^2+left(frac{m_2}{m_1} sin gamma_2 + frac{m_3}{m_1} sin gamma_3 right)^2 =
$$
$$
= frac{m_2^2}{m_1^2}+ frac{m_3^2}{m_1^2} + 2, frac{m_2m_3}{m_1^2} cos (gamma_2-gamma_3) .
$$
Обратим внимание, что естественным ограничением на условие задачи оказывается $ |cos (gamma_2 -gamma_3)| le 1 $, что равносильно $ m_1le m_2+m_{3} $ (сумма двух весов должна быть не меньше третьего; на самом деле условие того, что искомая точка $ P_{ast} $ будет отличаться от вершин $ P_1,P_2,P_3 $ более жесткое — см.

☟

НИЖЕ). Далее, из последнего равенства следует:
$$
Rightarrow sin^2 (gamma_2 -gamma_3) =frac{-m_1^4-m_2^4-m_3^4+2, m_1^2m_2^2+2, m_1^2m_3^2+2,m_2^2m_3^2}{4,m_2^2m_3^2} .
$$
Аналогичные равенства справедливы и для синусов оставшихся пар углов.

Отсюда получаем условие, которое должно выполняться в искомой точке $ P_{ast} $:
$$
frac{|sin (gamma_2 -gamma_3)|}{m_1} =frac{|sin (gamma_1 -gamma_3)|}{m_2} = frac{|sin (gamma_1 -gamma_2)|}{m_3} .
$$
Геометрический смысл разности $ gamma_1 -gamma_2 $ понятен из рисунка: это величина угла $ widehat{P_1 P_{ast}P_2} $. Можно образно сказать, что точки $ P_{1} $ и $ P_{2} $ «видно» из точки $ P_{ast} $ под углом $ gamma_2 -gamma_1 $.

В случае $ m_1=m_2=m_3=1 $ последнее равенство характеризует точку треугольника, которая известна под названием точки Ферма-Торричелли: это такая точка, из которой все его вершины «видны» под углом $ 2, pi/3 $. Точка Ферма-Торричелли не всегда существует — она имеется только у треугольников, углы которых не превосходят той же величины $ 2, pi/3 $.

Т

Теорема [3,4]. Точка Ферма-Торричелли существует только для треугольника $ P_{1}P_2P_3 $, у которого величина каждого угла меньше $ 2pi/3 $. В этом случае она единственна и в ней достигается

$$ min_{Pin mathbb R^2} (|PP_1|+|PP_2|+|PP_3|) , . $$
Если величина одного из углов треугольника $ ge 2pi/3 $, то минимум достигается при помещении точки $ P_{} $ в эту вершину.

П

Пример. Для точек $ P_1=(1,1), P_2=(3,5), P_3= (7,2) $ точка Ферма-Торричелли изображена на рисунке

Ее точные координаты приведены

☟

НИЖЕ .

♦

Вернемся к рассмотрению общего случая неравных весов.
На стороне $ P_{2}P_3 $ треугольника $ P_{1}P_2P_3 $ строится треугольник $ P_2P_3Q $, в котором

$$ |P_3Q|=frac{m_2}{m_1}|P_2P_3|, |P_2Q|=frac{m_3}{m_1}|P_2P_3| , $$
и который расположен по другую сторону от прямой $ P_2P_3 $ по отношению к треугольнику $ P_{1}P_2P_3 $.
Построенный треугольник очевидно оказывается подобным так называемому весовому треугольнику, т.е.
треугольнику с длинами сторон формально совпадающими с $ m_1,m_2,m_3 $.

Утверждается, что прямая $ QP_1 $ пересекает окружность, описанную вокруг треугольника $ P_2P_3Q $ в искомой точке $ P_{ast} $. В самом деле (см. рисунок ниже), по теореме синусов для треугольника $ P_2P_3Q $ будет выполнено:
$$
frac{sin nu_1 }{|P_2P_3|} =frac{sin nu_2 }{|P_3Q|} =frac{sin nu_3 }{|P_2Q|} quad iff quad frac{sin nu_1 }{m_1}=frac{sin nu_2 }{m_2}=frac{sin nu_3 }{m_3} .
$$
По построению точки $ P_{ast} $ будут иметь место соотношения:
$$ mu_1+nu_1=mu_2+nu_2= mu_3+nu_3= pi , $$
и, следовательно, ограничения на углы $ mu_1, mu_2, mu_3 $ оказываются такими же, как и на $ |gamma_3-gamma_2 |, |gamma_3-gamma_1 |, |gamma_2-gamma_1 | $.

Длина отрезка $ |P_1Q| $ позволяет определить величину минимального значения функции:
$$ m_1 |P_1Q| = m_1 |P_{ast} P_1|+m_2 |P_{ast} P_2|+ m_3 |P_{ast} P_3| = min_{Pin mathbb R^2} sum_{j=1}^3 m_j|PP_j| . $$
В предыдущих рассуждениях предполагается, что точка $ P_{ast} $ лежит внутри треугольника $ P_{1}P_2P_3 $. В противном случае, решением задачи будет одна из вершин треугольника.

П

Пример. Найти точку $ P_{ast} $ для конфигурации

$$
left{
begin{array}{c|c|c}
P_{1}=(2,6) & P_{2}=(1,1) & P_{3}=(5,1) \
m_{1}=2 & m_{2}=3 & m_{3}=4
end{array} right} .
$$

Решение. Здесь $ |P_2P_3|=4 $, следовательно $ |P_2Q|=4 cdot 2 = 8, |P_3Q|=4 cdot 3/2 = 6 $. Этими условиями определяем точку $ Q_{} $ — как одну из двух точек пересечения окружностей (радиуса $ 8_{} $ с центром в точке $ P_{2} $ и радиуса $ 6_{} $ с центром в $ P_3 $).

Её координаты: $ approx (6.5,-4.8) $. Проводим окружность через точки $ P_2,P_3,Q $. Прямая $ QP_1 $ пересекает ее в искомой точке $ P_{ast} approx (3.9, 1.4) $ при
минимальном значении для минимизируемой функции: $ F(x_{ast},y_{ast}) approx 23.4 $.

Точные значения приведены

☟

НИЖЕ.

♦

Для $ K=4 $ точек на плоскости геометрическое решение известно только для случая одинаковых весов.

Т

Теорема [Фаньяно]. Если точки $ P_{1},P_2,P_3, P_{4} $ образуют выпуклый четырехугольник, то

$$ min_{Pin mathbb R^2} left(|PP_1|+|PP_2|+|PP_3|+|PP_{4}| right)$$
достигается в точке $ P_{ast} $, лежащей на пересечении диагоналей четырехугольника:
$$ x_{ast}=frac{(x_1-x_3)(x_2y_4-y_2x_4)-(x_2-x_4)(y_3x_1-y_1x_3)}{(x_3-x_1)(y_2-y_4)-(x_2-x_4)(y_3-y_1)}, $$
$$ y_{ast}=frac{(y_1-y_3)(x_2y_4-y_2x_4)-(y_2-y_4)(y_3x_1-y_1x_3)}{(x_3-x_1)(y_2-y_4)-(x_2-x_4)(y_3-y_1)} , . $$
Если же точки $ P_{1},P_2,P_3, P_{4} $ не образуют выпуклый четырехугольник, и точка $ P_{i} $ лежит внутри треугольника, образованного тремя оставшимися точками, то минимум суммы расстояний достигается в точке $ P_{i} $.

Пусть $ {P_j= (x_{j},y_j)}_{j=1}^3 $. Обозначим
$$
r_{jell}=sqrt{(x_j-x_{ell})^2+(y_j-y_{ell})^2}=|P_jP_{ell}| quad npu {j,ell} subset {1,2,3} .
$$

Т

Теорема.[11] Пусть все углы треугольника $ P_{1}P_2P_3 $ меньше $ 2pi /3 $, или, что то же, выполнены условия:

$$ r_{12}^2+r_{13}^2+r_{12}r_{13}-r_{23}^2>0, r_{23}^2+r_{12}^2+r_{12}r_{23}-r_{13}^2>0, r_{13}^2+r_{23}^2+r_{13}r_{23}-r_{12}^2>0 . $$
Точка $ P_{ast} $ Ферма-Торричелли имеет координаты
$$
x_{ast}=frac{kappa_1kappa_2kappa_3}{2 sqrt{3} |S| d} left(frac{x_1}{kappa_1}+frac{x_2}{kappa_2}+frac{x_3}{kappa_3} right),
y_{ast}=frac{kappa_1kappa_2kappa_3}{2 sqrt{3} |S| d} left(frac{y_1}{kappa_1}+frac{y_2}{kappa_2}+frac{y_3}{kappa_3} right)
$$
при
$$ |P_1P_{ast}|+|P_2P_{ast}|+|P_3P_{ast}|= sqrt{d} . $$
Здесь
$$
d=frac{1}{sqrt{3}}(kappa_1+kappa_2+kappa_3)=frac{r_{12}^2+r_{13}^2+r_{23}^2}{2}+ sqrt{3}, |S| ,
$$
$$
left{
begin{array}{lcl}
kappa_1=frac{sqrt{3}}{2}(r_{12}^2+r_{13}^2-r_{23}^2)+|S| , \
kappa_2=frac{sqrt{3}}{2}(r_{23}^2+r_{12}^2-r_{13}^2)+|S| , \
kappa_3=frac{sqrt{3}}{2}(r_{13}^2+r_{23}^2-r_{12}^2)+|S| ;
end{array} right.
$$
и
$$
S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1=
$$
$$
=left|begin{array}{cc}
x_2-x_1 & x_3-x_1 \
y_2-y_1 & y_3-y_1
end{array}
right|=
left| begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_2 & x_3 \
y_1 & y_2 & y_3
end{array}
right| .
$$

Если выписать символьные представления для $ x_{ast} $ и $ y_{ast} $ в виде функций от параметров $ {x_j,y_j}_{j=1}^3 $, то можно осуществить сокращение на общий множитель $ |S| $ числителей и знаменателей получившихся в теореме дробей

☟

Т

Теорема.[5,11] Пусть все углы треугольника $ P_{1}P_2P_3 $ меньше $ 2pi /3 $.
Точка $ P_{ast} $ Ферма-Торричелли имеет координаты

$$
x_{ast}=frac{X}{2sqrt{3}d}, y_{ast}= frac{Y}{2sqrt{3}d}
$$
при
$$ |P_1P_{ast}|+|P_2P_{ast}|+|P_3P_{ast}|= sqrt{d} . $$
Здесь
$$ d=frac{r_{12}^2+r_{13}^2+r_{23}^2}{2}+sqrt{3} cdot | S | ; $$
$$
X=sqrt{3} [x_1r_{23}^2+x_2r_{13}^2+x_3r_{12}^2] +(x_1+x_2+x_3) cdot |S|+
$$
$$
+3 operatorname{sign} (S) [(y_2-y_1)(x_1x_2+y_1y_2)+(y_1-y_3)(x_1x_3+y_1y_3)+(y_3-y_2)(x_2x_3+y_2y_3)];
$$
$$
Y=sqrt{3} [y_1r_{23}^2+y_2r_{13}^2+y_3r_{12}^2]+ (y_1+y_2+y_3) cdot |S| —
$$
$$
-3 operatorname{sign} (S)[(x_2-x_1)(x_1x_2+y_1y_2)+(x_1-x_3)(x_1x_3+y_1y_3)+(x_3-x_2)(x_2x_3+y_2y_3)] ;
$$
$$
S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1=
$$
$$
=left|begin{array}{cc}
x_2-x_1 & x_3-x_1 \
y_2-y_1 & y_3-y_1
end{array}
right|=
left| begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_2 & x_3 \
y_1 & y_2 & y_3
end{array}
right| .
$$

П

Пример. При $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ будет:

$$ x_{ast}=frac{2}{687} left( 1029 + 79 sqrt{3}right) approx 3.3939,qquad y_{ast}=frac{1}{687} left( 1053 + 647 sqrt{3} right) approx 3.1639 , $$
$$ |P_{ast}P_1|+|P_{ast}P_2|+|P_{ast}P_3| = sqrt{41+22sqrt{3}}approx 8.8941 . $$
При $ P_1=(1,2),P_2=(3,3),P_3=(4,1) $ :
$$ x_{ast}=frac{1}{6}(15+sqrt{3}) approx 2.7886,qquad y_{ast}=frac{1}{2}(3+sqrt{3}) approx 2.3660 ; $$
$$ |P_{ast}P_1|+|P_{ast}P_2|+|P_{ast}P_3| = sqrt{5,(2+sqrt{3})}approx 4.3197 , . $$

Проверка равенства
$$
frac{(x_{ast}-x_1)(x_{ast}-x_2)+(y_{ast}-y_1)(y_{ast}-y_2)}{sqrt{((x_{ast}-x_1)^2+(y_{ast}-y_1)^2)((x_{ast}-x_2)^2+(y_{ast}-y_2)^2)}}=-frac{1}{2}
$$
произведена.

Получено только для случая $ K=3 $.

Т

Теорема.[11] Обозначим величину угла треугольника $ P_{1}P_2P_3 $ при вершине $ P_{j} $ через $ alpha_j $. Если нарушено $ j $-е из трех условий

begin{align*}
m_2^2+m_3^2+2, m_2m_3 cos alpha_1 & > m_1^2 , \
m_1^2+m_3^2+2, m_1m_3 cos alpha_2 & > m_2^2,\
m_1^2+m_2^2+2, m_1m_2 cos alpha_3 & > m_3^2,
end{align*}
то минимум функции
$$ F(x,y)=sum_{j=1}^3 m_j sqrt{(x-x_j)^2+(y-y_j)^2} $$
достигается в точке $ P_{j}=(x_j,y_j) $. Если все неравенства выполняются, то $ min F(x,y) $ достигается в точке $ P_{ast} $ с координатами:
$$
x_{ast}=frac{K_1K_2K_3}{4 |S| sigma d} left(frac{x_1}{K_1}+frac{x_2}{K_2}+frac{x_3}{K_3} right),
y_{ast}=frac{K_1K_2K_3}{4 |S| sigma d} left(frac{y_1}{K_1}+frac{y_2}{K_2}+frac{y_3}{K_3} right) .
$$
при
$$
F(x_{ast},y_{ast})=min_{(x,y)} F(x,y)=sqrt{d} .
$$
Здесь
$$
d= 2, |S| sigma +
$$
$$
+frac{1}{2}left[m_1^2(r_{12}^2+r_{13}^2-r_{23}^2)+
m_2^2(r_{23}^2+r_{12}^2-r_{13}^2)+m_3^2(r_{13}^2+r_{23}^2-r_{12}^2) right] ;
$$
$$
r_{jell}=sqrt{(x_j-x_{ell})^2+(y_j-y_{ell})^2}=|P_jP_{ell}| quad npu {j,ell} subset {1,2,3} ;
$$
$$
S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1=
$$
$$
=left|begin{array}{cc}
x_2-x_1 & x_3-x_1 \
y_2-y_1 & y_3-y_1
end{array}
right|=left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_2 & x_3 \
y_1 & y_2 & y_3
end{array}
right| ;
$$
$$
sigma= frac{1}{2} sqrt{-m_1^4-m_2^4-m_3^4+2,m_1^2m_2^2+2,m_1^2m_3^2+2,m_2^2m_3^2} ;
$$
$$
left{
begin{array}{ccc}
K_1&=&(r_{12}^2+r_{13}^2-r_{23}^2)sigma+(m_2^2+m_3^2-m_1^2) |S| , \
K_2&=&(r_{23}^2+r_{12}^2-r_{13}^2)sigma+(m_1^2+m_3^2-m_2^2) |S| , \
K_3&=&(r_{13}^2+r_{23}^2-r_{12}^2)sigma+(m_1^2+m_2^2-m_3^2) |S| .
end{array}
right.
$$

П

Пример. Для конфигурации

$$
left{begin{array}{c|c|c}
P_{1}=(2,6) & P_{2}=(1,1) & P_{3}=(5,1) \
m_{1}=2 & m_{2}=3 & m_{3}=4
end{array}
right}
$$
точка $ P_{ast} $ имеет координаты
$$
x_{ast}=frac{4103+1833 sqrt{15}}{2866}approx 3.9086 , y_{ast} =frac{29523-4481 sqrt{15}}{8598}approx 1.4152 , .
$$
Минимальное значение для функции:
$$ min F(x,y)= m_1|P_{ast}P_1|+m_2|P_{ast}P_2|+m_3|P_{ast}P_3|= 2sqrt{79+15sqrt{15}} approx 23.4174 , . $$

♦

Если выписать символьные представления для $ x_{ast} $ и $ y_{ast} $ в виде функций от параметров $ {x_j,y_j,m_j}_{j=1}^3 $, то можно осуществить сокращение на общий множитель $ |S| $ в числителе и в знаменателе получившихся в теореме дробей.
Правда, результат такого сокращения выглядит довольно громоздко: см.

☞

ЗДЕСЬ.

В случае $ K>3 $ точек аналитическое решение для обобщенной задачи Ферма-Торричелли вряд ли может быть получено. Тем не менее, можно попытаться продвинуться аналитикой возможно дальше, именно:
свести поиск координаты точки $ P_{ast} $ к решению системы полиномиальных (алгебраических) уравнений и попытаться применить к этой системе методы исключения переменных.

П

Пример. Выяснить динамику поведения точки $ P_{ast} $ для конфигурации

$$
left{
begin{array}{c|c|c|c}
P_{1}=(1,1) & P_{2}=(3,5) & P_{3}=(7,2) & P_{4}=(6,6) \
m_{1}=1 & m_{2}=1 & m_{3}=1 & m_{4}=m
end{array}
right}
$$
в зависимости от изменения параметра $ m_{} $.

Решение. При каждом конкретном значении параметра $ m_{} $ координаты стационарной точки $ P_{ast} $ можно найти применением численных методов, но нас интересует хоть какое-то функциональное представление для $ P_{ast} (m) $.

Градиентную систему уравнений
$$
left{ begin{array}{lll}
frac{ partial F}{partial x} &= frac{(x-1)}{sqrt{(x-1)^{2}+(y-1)^2}}+frac{(x-3)}{sqrt{(x-3)^{2}+(y-5)^2}}+frac{(x-7)}{sqrt{(x-7)^{2}+(y-2)^2}}+ frac{m(x-6)}{sqrt{(x-6)^2+(y-6)^2}} & = 0 \
frac{partial F}{partial y} &= frac{(y-1)}{sqrt{(x-1)^{2}+(y-1)^2}}+frac{(y-5)}{sqrt{(x-3)^{2}+(y-5)^2}}+frac{(y-2)}{sqrt{(x-7)^{2}+(y-2)^2}}+ frac{m(y-6)}{sqrt{(x-6)^2+(y-6)^2}} & = 0
end{array}
right.
$$
преобразуем к алгебраической. Это можно сделать различными методами и результат существенно зависит от организации процесса (т.е. алгебраическая система, включающая в себя множество решений исходной, определяется не единственным образом). Мы укажем пока только конечный результат (один из возможных):
$$ F_1(x,y,m)=0, F_2(x,y,m)=0 ; $$
здесь $ F_{1} $ и $ F_{2} $ полиномы степени $ 6_{} $ по каждой переменной $ x_{} $ или $ y_{} $ и степени $ 12_{} $ по обеим переменным. Из этой системы, посредством вычисления результанта, можно исключить переменные $ x_{} $ или $ y_{} $ и получить алгебраические уравнения вида
$$ mathcal X(x,m)=0, mathcal Y(y,m)=0, $$
которым удовлетворяют координаты стационарных точек при каждом фиксированном значении $ m_{} $. Оказывается, эти уравнения можно упростить (отбросить посторонние сомножители), сведя к уравнениям степени $ 12 $ по каждой из переменных $ x_{} $ или $ y_{} $.
Их выражения

☞

ЗДЕСЬ.

Дальнейшее упрощение вряд ли возможно: уравнения неприводимы над $ mathbb Q_{} $, и, скорее всего, неразрешимы в радикалах.

Можно пойти другим путем: исключать параметр $ m_{} $ с целью нахождения неявного представления кривой, на которой расположены стационарные точки при всех возможных значениях $ m_{} $. Результант $ mathcal R_m(F_1,F_2) $ оказывается полиномом степени $ 96 $ по $ x_{} $ и $ y_{} $, и этот полином факторизуется в виде
$$ 65536 (2x-y-1)^8(x^2-14x+53-4y+y^2)^8(x^2-12,x+72-12y+y^2)^8 Phi_0^2(x,y) Phi^2(x,y) . $$
Собственно кривая стационарных точек задается одним множителем:
$$ Phi(x,y) = 0 $$
при
$$
Phi(x,y)
=3,y(-7,y+10,x)(8,x-y)(2,x-9,y)(x^2+y^2)^4+
$$
$$
+8,(160,x^5-2594,x^4y+10117,x^3y^2+3152,x^2y^3-6209,xy^4+183,y^5)(x^2+y^2)^3-
$$
$$
-4,(10144,x^6-106368,x^5y+344359,x^4y^2+303368,x^3y^3+32554,x^2y^4-193808,xy^5-16853,y^6)(x^2+y^2)^2
$$
$$
+dots -1152, (2823793,x^2-22813720,xy-56866,y^2)+4409856 (1491,x+1234,y)-2110116096 .
$$
Полное выражение для функции $ Phi $ и картина всей кривой $ Phi=0 $ целиком достаточно сложны: см.

☞

ЗДЕСЬ. На рисунке выделена только ветвь, которая соответствует реальной динамике стационарной точки.

«Контрольные» точки на этой ветви:

x

$ left(frac{2}{687}(1029 + 79sqrt{3}),frac{1}{687}(1053 + 647sqrt{3}) right) $ — точка Ферма-Торричелли треугольника $ P_1P_2P_{3} $, соответствует значению $ m=0 $;

x

$ left(frac{29}{7},frac{29}{7}right) $ — точка пересечения диагоналей четырехугольника $ P_1P_2P_3P_4 $, соответствует значению $ m_{}=1 $ (см.

☞

теорему Фаньяно);

♦

$ (6,6) $ — вершина $ P_{4} $, соответствует значению $ m approx 2.4436 $ (точное значение

☞

ЗДЕСЬ);

♦

$ (1,1) $ — вершина $ P_{1} $, соответствует значению $ m approx -2.4184 $ (вообще говоря, в постановке задачи говорится только о положительных значениях весов, но почему бы не осуществить аналитическое продолжение? );

x

$ (frac{11}{3},frac{11}{3}) $, соответствует $ m=1-sqrt{2/5} approx 0.3675 $.

Т

Теорема. Пусть точки $ {P_j}_{j=1}^K subset mathbb R^n $ все различны. Минимум функции
$$ F(P)=sum_{j=1}^K m_j |PP_j| $$
существует и единствен. При этом

1.

если существует точка $ P_{i} $ такая, что выполняется условие
$$
left|sum_{j=1 atop j ne i}^K m_j frac{P_jP_i}{|P_jP_i|} right| le m_i , $$
то $ min F(P) $ достигается в точке $ P_{i} $;

2.

если для любого значения $ i in {1,dots,K} $ выполняется условие
$$
left|sum_{j=1 atop j ne i}^K m_j frac{P_jP_i}{|P_jP_i|} right| > m_i , $$
то $ min F(P) $ достигается в точке $ P_{ast} $, удовлетворяющей градиентной системе уравнений
$$ sum_{j=1}^K m_j frac{PP_j}{|PP_j|}=mathbb O_{ntimes 1}, ; $$
и, в этом случае, $ P_{ast} notin {P_j}_{j=1}^K $.

Доказательство

☞

ЗДЕСЬ

П

Пример. При каких значениях параметра $ m_{} $ в конфигурации

$$
left{
begin{array}{c|c|c|c}
P_{1}=(1,1) & P_{2}=(3,5) & P_{3}=(7,2) & P_{4}=(6,6) \
m_{1}=1 & m_{2}=1 & m_{3}=1 & m_{4}=m
end{array}
right}
$$
$ min sum_{j=1}^4 m_j|PP_j| $ достигается в точке $ P_4 $?

Решение. Формируем условие
$$
left| m_1 frac{(1,1)- (6,6)}{sqrt{50}}+m_2frac{(3,5)- (6,6)}{sqrt{10}}+m_3 frac{(7,2)- (6,6)}{sqrt{17}} right| le m_4 .
$$
Ответ. При $ m ge sqrt{3+4/sqrt{5}+3sqrt{2/17}+sqrt{2/85}} approx 2.4436 $.

Заметим, что попадание точки $ P_{ast} $ в вершину $ P_{i} $ происходит при значениях $ m_{i} $ меньших, чем сумма оставшихся весов.

=>

В случае $ n=2, K=3 $ условия теоремы переформулируются в терминах углов $ alpha_1,alpha_2, alpha_3 $ треугольника $ P_1P_2P_{3} $. Так, например, условие

2

эквивалентно

$$
m_2^2+m_3^2+2, m_2m_3 cos alpha_1 > m_1^2 , m_1^2+m_3^2+2, m_1m_3 cos alpha_2 > m_2^2, m_1^2+m_2^2+2, m_1m_2 cos alpha_3 > m_3^2, .
$$
Если $ m_1=m_2=m_3 $, то эти условия означают, что все углы треугольника меньше $ 2pi/3 $.
В общем же случае (не обязательно равных весов) этим условиям можно придать следующую геометрическую интерпретацию. Их выполнение означает, что рассматривая величины весов $ m_1,m_2,m_3 $ в качестве длин отрезков, мы можем построить из этих отрезков треугольник — он так и называется: «весовой треугольник» [1].

Обозначим углы этого треугольника $ beta_1, beta_2, beta_3 $ в соответствии с рисунком.
Тогда, по теореме косинусов, получаем:
$$ cos alpha_j+ cos beta_j > 0 quad npu quad jin {1,2,3} , . $$

Рассмотрим задачу в $ mathbb R^{n}_{} $ сначала для случая одинаковых весов $ m_1=dots=m_K=1 $. Перепишем градиентную систему уравнений
$$
frac{P-P_1}{|PP_1|}+dots+frac{P-P_K}{|PP_K|}= mathbb O_{ntimes 1},
$$
задающую стационарные точки функции $ F(P) $, в эквивалентном виде
$$
P=underbrace{left(frac{P_1}{|PP_1|}+dots+frac{P_K}{|PP_K|} right) bigg/ left(frac{1}{|PP_1|}+dots+frac{1}{|PP_K|} right)}_{=Phi(P)} , .
$$
Решать последнюю систему будем методом простой итерации. Возьмем в качестве начального приближения произвольную точку $ P^{(0)} notin {P_j}_{j=1}^K $ и строим последовательность по рекурсивной формуле
$$
P^{(k)}=Phi(P^{(k-1)}) quad npu quad k in mathbb N .
$$
Утверждается, что эта последовательность сходится к точке $ P_{ast} $, являющейся точкой минимума функции $ F(P)=sum_{j=1}^K |PP_j| $.

Метод известен как алгоритм Вайсфельда [14].

П

Пример. Для $ P_1=(1,1), P_2=(3,5), P_3=(7,2) $ возьмем $ P^{(0)}=(2,2) $. Итерационная последовательность

$$
left(begin{array}{c} 2 \ 2 end{array} right) to left(begin{array}{c} 2.4979 \ 2.1974 end{array} right)
to left(begin{array}{c} 2.8581 \ 2.4862 end{array} right) to left(begin{array}{c} 3.1122 \ 2.7295 end{array} right)
to dots to P^{(7)} =left(begin{array}{c} 3.3_{displaystyle 879} \ 3.1_{displaystyle 089} end{array} right) to dots
$$
сходится к точке Ферма-Торричелли $ P_{ast}approx (3.3939, 3.1639 ) $.

♦

П

Пример. Для $ P_1=(1,1,0), P_2=(5,1,0), P_3=(2,6,0), P_4=(3,3,5) $ возьмем $ P^{(0)}=(1,1,1) $. Итерационная последовательность

$$
left(begin{array}{c} 1 \ 1 \ 1 end{array} right)
to left(begin{array}{c} 1.9583 \ 1.8361 \ 0.6226 end{array} right)
to left(begin{array}{c} 2.3007 \ 2.1007 \ 0.7319 end{array} right)
to left(begin{array}{c} 2.5077 \ 2.2665 \ 0.8386 end{array} right)
to dots
to P^{(7)}= left(begin{array}{c} 2.6_{displaystyle 781} \ 2.42_{displaystyle 28} \ 0.9_{displaystyle 552} end{array} right) to dots
$$
сходится к точке $ P_{ast} approx (2.6823, 2.4298, 0.9607) $.

♦

Проблемы сходимости возникают в случае, когда искомая точка $ P_{ast} $ близка к одной из $ {P_j}_{j=1}^K $.

П

Пример. Для

$$ P_1=(0,0), P_2=(1,0), P_3=(-4,7) $$
координаты точки Ферма-Торричелли: $ P_{ast}approx (0.0023,0.0039) $. Итерационная последовательность, стартующая из $ P^{(0)}=(0,1) $, не дает этой точности при $ 200 $ итерациях.

♦

Метод очевидным образом обобщается и на случай, когда веса в конфигурации не обязательно одинаковы: в рекурсивной формуле следует взять
$$
Phi(P)=left(frac{m_1P_1}{|PP_1|}+dots+frac{m_KP_K}{|PP_K|} right) bigg/ left(frac{m_1}{|PP_1|}+dots+frac{m_K}{|PP_K|} right) .
$$

Задача. Подобрать величины весов $ {m_j}_{j=1}^K $ так, чтобы минимум функции $ displaystyle F(P)=sum_{j=1}^K m_j |PP_j| $ находился в наперед заданной точке $ P_{ast} notin {P_j}_{j=1}^K $.

В отличие от «прямой» задачи, обратная имеет довольно простое решение. Начнем рассмотрение со случая плоскости: $ n=2, K=3 $.

Т

Теорема [11]. Пусть вершины треугольника $ P_{1}P_2P_3 $ пронумерованы против часовой стрелки. Тогда для значений

$$
m_1^{ast} = |P_{ast}P_1| cdot left|
begin{array}{ccc}
1 & 1 & 1 \
x_{ast} & x_2 & x_3 \
y_{ast} & y_2 & y_3
end{array}
right|,
m_2^{ast} = |P_{ast}P_2| cdot left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_{ast} & x_3 \
y_1 & y_{ast} & y_3
end{array}
right|,
m_3^{ast} = |P_{ast}P_3| cdot left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_2 & x_{ast} \
y_1 & y_2 & y_{ast}
end{array}
right|
$$
функция
$$ F(x,y) = sum_{j=1}^3 m_{j}^{ast} sqrt{(x-x_j)^2+(y-y_j)^2} $$
имеет стационарную точкой точку $ P_{ast}=(x_{ast},y_{ast}) $. Если последняя выбирается внутри треугольника
$ P_{1}P_2P_3 $, то величины $ m_1^{ast},m_2^{ast},m_3^{ast} $ все положительны и
$$
F(x_{ast},y_{ast})=min_{(x,y)in mathbb R^2} F(x,y)=
left|
begin{array}{cccc}
1 & 1 & 1 & 1\
x_{ast} & x_1 & x_2 & x_3 \
y_{ast} & y_1 & y_2 & y_3 \
x_{ast}^2+y_{ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2
end{array}
right| .
$$

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

☞

ЗДЕСЬ.

Решение обратной задачи определяется с точностью до сомножителя, т.е. тройка решений $ (m_1,m_2,m_3) $ определяется отношением $ m_1:m_2:m_3 $. С учетом этого обстоятельства, решение обратной задачи единственно.

П

Пример. Поместить в точках $ P_{1}=(2,6),P_{2}=(1,1), P_{3}=(5,1) $ соответствующие веса $ {m_j^{ast}} $ так, чтобы точка минимума
функции $ F(x,y) $ находилась бы в точке

$$ P_{ast} = left(frac{ 4103+1833 sqrt{15}}{2866} , frac{29523-4481 sqrt{15}}{8598} right) . $$

Решение. Формулы из теоремы дают:
$$
left{begin{array}{ccl}
m_1^{ast}&=& displaystyle frac{2(20925-4481sqrt{15})}{18481401}sqrt{316380606+35999826sqrt{15}} ,\
m_2^{ast}&=& displaystyle frac{2(15105-2342sqrt{15})}{6160467}sqrt{75400161-9169767sqrt{15}} , \
m_3^{ast}&=& displaystyle frac{8(-1185+15988sqrt{15})}{18481401}sqrt{8335761-2050623sqrt{15}} ,
end{array}
right.
$$
при
$$
F(x_{ast},y_{ast})=frac{1}{4299}(-333980+193436sqrt{15}) .
$$
Сравним этот результат с полученным

☝

ВЫШЕ. В соответствии с замечанием, должно выполняться:
$ m_1^{ast} : m_2^{ast} : m_3^{ast} = 2 : 3 : 4 $.
А проверьте!

♦

§

Обобщение результата в многомерный случай $ n>2 $ для числа точек $ K=n+1 $

☞

ЗДЕСЬ.

Задача. Пусть заданы точки $ P_1,dots,P_K $ на плоскости. Требуется построить связную систему $ mathbf L_{} $ прямолинейных отрезков на той же плоскости, чтобы

1.

любые две точки $ P_{j} $ и $ P_{ell} $ могли быть связаны ломаной линией, звенья которой входили бы в состав системы $ mathbf L_{} $;

2.

общая длина всей системы $ mathbf L_{} $ была наименьшей.

Такая система $ mathbf L_{} $ называется минимальным деревом Штейнера, ее построение и применения см. в [3,4].

На первый взгляд кажется, что эта задача эквивалентна задаче Ферма-Торричелли в случае одинаковых весов и речь идет о поиске единственной точки $ P_{ast} $ на плоскости. На самом деле, решение этой задачи для случая $ K ge 4 $ предполагает построение нескольких вспомогательных точек.

П

Пример. Построить минимальное дерево Штейнера для точек
$$ P_1=(0,3), P_2=(0,0), P_3=(4,0), P_4=(4,3) , . $$

Решение. Будем пробовать варианты решения задачи, последовательно добавляя вспомогательные точки. Если не добавлять дополнительных точек вообще, то эта задача относится к классу задач построения минимального покрывающего дерева⁷⁾. В такой постановке решением рассматриваемого примера будет ломаная $ P_1P_2P_3P_4 $ длиной $ 3+4+3=10 $.

Если разрешено добавить одну дополнительную точку, то решением задачи, в соответствии с

☝

теорему Фаньяно, будет система из двух диагоналей прямоугольника:

Тем не менее, выигрыша в длине дерева не получим: $ 5+5=10 $. Но если разрешено добавлять две дополнительных точки, то расположив их в
$ P_{ast}=left(frac{sqrt{3}}{2},frac{3}{2} right) $ и $ P_{ast ast}=left(4-frac{sqrt{3}}{2},frac{3}{2} right) $

получим суммарную длину равной $ 4+ 3sqrt{3} approx 9.196152 $.

Можно ли улучшить этот результат добавлением еще большего количества дополнительных точек? Ответ отрицателен: оказывается, что для произвольной конфигурации системы $ {P_j}_{j=1}^4 $ количество дополнительных точек, необходимых для решения задачи о минимальном дереве, никогда не превысит двух.

♦

В рассмотренном примере точка $ P_{ast} $ является точкой Ферма-Торричелли для треугольника $ P_1 P_2 P_{ast ast} $, а точка $ P_{ast ast} $ —
точкой Ферма-Торричелли для треугольника $ P_3 P_4 P_{ast } $. Это свойство оказывается принципиальным для решения общей задачи: для любой конфигурации точек $ { P_j }_{j=1}^K subset mathbb R^2 $ минимальное дерево Штейнера является графом, соединяющим эти точки с дополнительными узлами графа, составляющими некоторое множество $ { S_{ell} }_{ell=1}^M $. Мощность этого дополнительного множества находится в пределах
$$ 0 le M le K-2 , ,$$
и, при условии, что оно не пусто, любой его элемент является точкой Ферма-Торричелли для некоторой тройки точек из объединения $ { P_j }_{j=1}^K bigcup { S_{ell} }_{ell=1}^M $. Степень каждой вершины $ { P_j }_{j=1}^K $ графа равна либо $ 1_{} $ либо $ 2_{} $.

§

Задача о минимальном дереве Штейнера обсуждается

☞

ЗДЕСЬ.

Для случая $ n=2_{} $ рассмотрим задачу о линиях уровня функции
$$
F(x,y)= sum_{j=1}^{K} sqrt{(x-x_j)^2+(y-y_j)^2} ,
$$
т.е. о кривых $ F(x,y)=c $ при различных значениях $ c_{} $. В случае $ K=2 $ решение задачи хорошо известно — это либо эллипс с фокусами в точках $ P_1=(x_1,y_1),P_2=(x_2,y_2) $,
либо отрезок, соединяющий эти точки, либо пустое множество (мнимый эллипс). Что за кривые соответствуют случаям $ K ge 3 $? Например, каково геометрическое место точек, сумма расстояний от которых до фиксированных точек $ P_1,P_2,P_3 $ является постоянной величиной? Этот вопрос был задан Декартом Ферма в 1638 г. (и именно отсюда возникла у Ферма постановка задачи о поиске минимума функции $ F_{} $).

Эти кривые называются мультифокусными (мультифокальными) эллипсами,полиэллипсами или обобщенными эллипсами. В немецком языке известны также под названием Tschirnhaus’sche Eikurve — яйцеобразные кривые Чирнгауза .
Они могут считаться алгебраическими кривыми — последовательным возведением их уравнений в квадрат можно избавиться от радикалов.

П

Пример. Для $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ семейство трехфокусных эллипсов (алгебраических кривых порядка $ 8_{} $) выглядит так (числа на кривых — значения константы $ c_{} $):

Каким значениям $ c_{} $ соответствуют кривые, проходящие через точки $ P_1, P_2, P_3 $ ?

♦

В случае когда веса $ { m_j } $ могут быть различными, линии уровня функции
$$
F(x,y)= sum_{j=1}^{K} m_jsqrt{(x-x_j)^2+(y-y_j)^2} ,
$$
не имеют установившегося названия. В случае $ K=2 $ в литературе встречаются под названием овалы Декарта; сам Декарт называл их эллипсами второго рода. Если $ Kge 3 $ и величины весов $ { m_j } $ рационально соизмеримы, то этот случай может быть быть рассмотрен как предельный случай мультифокусного эллипса — когда некоторые из фокусов сливаются в один. Этими кривыми в середине XIX века интересовался (из любознательности) один шотландский ученый [7]. В случае $ K=3 $ кривые
известны в экономической географии под названием изодапан⁹⁾; каждая такая кривая состоит из точек одинаковой суммарной стоимости транспортных перевозок до них из $ {P_j} $.

A

Анимация трехмерного аналога мультифокусного эллипса

☞

ЗДЕСЬ (470 Kb).

Задача 1. Построить максимальный равносторонний треугольник $ Q_1Q_2Q_3 $, описанный вокруг заданного треугольника $ P_{1}P_{2}P_3 $ (на каждой стороне треугольника $ Q_{1}Q_{2}Q_3 $ должна лежать одна вершина треугольника $ P_1P_2P_3 $).

Т

Теорема. Пусть все углы треугольника $ P_{1}P_{2}P_3 $ меньше $ 2pi/3 $. Высота искомого треугольника $ Q_1Q_2Q_3 $ равна $ |P_{ast}P_1|+|P_{ast}P_2|+|P_{ast}P_3| $, где $ P_{ast} $ — точка Ферма-Торричелли треугольника $ P_{1}P_{2}P_3 $. Стороны треугольника $ Q_1Q_2Q_3 $ перпендикулярны прямым $ P_{ast}P_1, P_{ast}P_2 $ и $ P_{ast}P_3 $.

Задача 2. Построить минимальный равносторонний треугольник $ R_1R_2R_3 $, вписанный в заданный треугольник $ P_{1}P_{2}P_3 $ (на каждой стороне треугольника $ P_{1}P_{2}P_3 $ должна лежать одна вершина треугольника $ R_1R_2R_3 $).

На удивление, ссылок в интернете на решение задачи 2 я не нашел, за исключением

☞

ЭТОЙ. Задача похожа на задачу Фаньяно о построении произвольного треугольника минимального периметра, вписанного в данный остроугольный [4]; однако требование равносторонности треугольника в условии задачи существенно меняет ее решение.

Т

Теорема. Пусть все углы треугольника $ P_{1}P_{2}P_3 $ меньше $ 2pi/3 $. Стороны искомого треугольника $ R_1R_2R_3 $ параллельны сторонам треугольника $ Q_1Q_2Q_3 $,
решающего предыдущую задачу. Имеет место соотношение между площадями трех треугольников — исходного, максимального описанного и минимального вписанного:
$$
frac{ S_{triangle Q_1Q_2Q_3}}{ S_{triangle P_1P_2P_3}}=frac{ S_{triangle P_1P_2P_3}}{S_{triangle R_1R_2R_3}} .
$$

Задача. Найти стационарные точки функции
$$
F(P)= sum_{j=1}^K m_j left|PP_j right|^L .
$$
Здесь $ {P,P_1,dots,P_K} subset mathbb R^n $, $ L_{} $ предполагается вещественным ненулевым числом, а величины $ { m_{j} }_{j=1}^K $ — произвольными вещественными числами (не обязательно положительными).

В случае $ L=1 $ мы получаем обобщенную задачу Ферма-Торричелли, рассмотренную выше. В случае $ L=2 $ решением задачи является единственная точка
$$ P_{ast}= frac{sum_{j=1}^K m_jP_j}{ sum_{j=1}^K m_j} $$
— точка глобального минимума функции $ F(P) $. В случае всех положительных $ {m_j}_{j=1}^K $ и $ nin {2,3} $ точка $ P_{ast} $ является центром масс (барицентром) системы материальных точек, расположенных в точках $ {P_j}_{j=1}^K $.

Нас интересует решение задачи для других показателей $ L_{} $. Поставленной задаче можно придать физический смысл. Пусть в пространстве имеется конфигурация
$$
left{begin{array}{c|c|c} P_1 & dots & P_K \
m_1 & dots & m_K
end{array}
right}
$$
из $ K_{} $ фиксированных (неподвижных) точечных заряженных частиц, которые воздействуют на пробный точечный единичный заряд величины, помещенный в точку $ P_{} $; при этом сила воздействия $ j_{} $-го заряда прямо пропорциональна величине заряда $ m_{j} $ и пропорциональна некоторой степени $ L_{} $ расстояния от этого заряда до пробного. Требуется найти точку $ P_{ast} in mathbb R^{n}_{} $, при помещении в которую пробного заряда, последний будет неподвижен (находиться в положении равновесия).

Особый интерес представляет частный случай поставленной задачи: $ L=-1 $. Этому случаю соответствует два физических потенциала — кулоновский (электростатический) и ньютоновский (гравитационный)¹⁰⁾.

Стационарные точки этого семейства потенциалов задаются градиентной системой уравнений
$$
left{frac{partial F}{partial x_{ell}}= L sum_{j=1}^{K} m_j |PP_j|^{L-1} frac{(x_{ell}-x_{jell})}{|PP_j|} = 0 right}_{ell=1}^n ,
quad npu quad begin{array}{c} {P_j=(x_{j1},dots,x_{jn})}_{j=1}^K, \ P=(x_1,dots,x_n) end{array} ,
$$
которая при четных значениях $ L_{} $ является алгебраической (или может быть немедленно приведена к алгебраической в случае отрицательных $ L_{} $); в остальных же случаях она будет содержать радикалы, от которых можно избавиться только последовательным возведением уравнений в квадрат. Уже для случая кулоновского потенциала $ L=-1, n=2, K=3 $ это приводит к алгебраическим уравнениям высокой степени с громоздкими коэффициентами.

П

Пример. Пусть $ P_1=(1,1), P_2=(5,1) , P_3=(2,6) $.
Проанализировать поведение множества стационарных точек функции

$$
F(x,y)=frac{1}{sqrt{(x-1)^2+(y-1)^2}}+ frac{m_2}{sqrt{(x-5)^2+(y-1)^2}}+frac{m_3}{sqrt{(x-2)^2+(y-6)^2}}
$$
в зависимости от значений $ m_2, m_3 $, рассматриваемых в качестве параметров.

Решение. Градиентная система уравнений
$$
begin{array}{rrr}
displaystyle frac{x-1}{sqrt{(x-1)^2+(y-1)^2}^3}& displaystyle +frac{m_2(x-5)}{sqrt{(x-5)^2+(y-1)^2}^3}& displaystyle +frac{m_3(x-2)}{sqrt{(x-2)^2+(y-6)^2}^3}=0, , \
displaystyle frac{y-1}{sqrt{(x-1)^2+(y-1)^2}^3}& displaystyle +frac{m_2(y-1)}{sqrt{(x-5)^2+(y-1)^2}^3}& displaystyle +frac{m_3(y-6)}{sqrt{(x-2)^2+(y-6)^2}^3}=0 ,
end{array}
$$
может быть преобразована в алгебраическую в ходе следующей процедуры. Обозначим $ A_1, A_2 $ и $ A_3 $ слагаемые в любом из этих уравнений.
Последовательное возведение в степень по схеме
$$ A_1+A_2+A_3=0 quad Rightarrow quad (A_1+A_2)^2=A_3^2 quad Rightarrow quad (2, A_1A_2)^2 = (A_3^2-A_1^2 — A_2^2)^2 $$
приводит систему к алгебраической
$$
F_1(x,y,m_2,m_3)=0, F_2(x,y,m_2,m_3)=0 .
$$
Здесь $ F_{1} $ и $ F_{2} $ — полиномы степени $ 28 $ по переменным $ x_{} $ и $ y_{} $ с коэффициентами порядков до $ 10^{19} $. Нахождение всех решений
этой системы — даже для конкретных (фиксированных) значений параметров $ m_2 $ и $ m_3 $ — становится вычислительно сложной задачей. А ведь требуется решить еще более
сложную задачу: проследить динамику этого множества при изменении параметров!

Сложность поставленной задачи — по сравнению с обобщенной задачей Ферма-Торичелли — заключается еще и в том, что что число вещественных решений системы больше единицы;
в зависимости от значений параметров, число стационарных точек — от $ 2_{} $ до $ 4_{} $.

♦

Гипотеза [Максвелл] [8,15]. Число стационарных точек кулоновского поля любой конфигурации $ K_{} $ стационарных зарядов в $ mathbb R^3 $ не превосходит $ (K-1)^2 $. Не доказана¹¹⁾.

Что общего у поставленной в начале пункта задачи с обобщенной задачей Ферма-Торричелли? — То, что похожим образом решается обратная задача.
Рассмотрим сначала плоский случай.

Т

Теорема [12, 13]. Пусть точки $ P_{1}=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3) $ неколлинеарны. Тогда для значений

$$
m_1^{ast} = |P_{ast}P_1|^{2-L} left|
begin{array}{ccc}
1 & 1 & 1 \
x_{ast} & x_2 & x_3 \
y_{ast} & y_2 & y_3
end{array}
right|,
m_2^{ast} = |P_{ast}P_2|^{2-L} left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_{ast} & x_3 \
y_1 & y_{ast} & y_3
end{array}
right|,
m_3^{ast} = |P_{ast}P_3|^{2-L} left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_2 & x_{ast} \
y_1 & y_2 & y_{ast}
end{array}
right|
$$
функция
$$ F(x,y) = sum_{j=1}^3 m_{j}^{ast} |PP_j|^L $$
имеет стационарную точку $ P_{ast}=(x_{ast},y_{ast}) $. При этом
$$
F(x_{ast},y_{ast})=
left|
begin{array}{cccc}
1 & 1 & 1 & 1\
x_{ast} & x_1 & x_2 & x_3 \
y_{ast} & y_1 & y_2 & y_3 \
x_{ast}^2+y_{ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2
end{array}
right| .
$$

Доказательство фактически повторяет приведенное

☞

ЗДЕСЬ.

Подчеркнем, что, фактически, этот результат решает задачу теории управления: подбором параметров системы удается обеспечить наперед заданное положение равновесия в кулоновском (ньютоновском) поле. Тут же возникает (традиционный для теории управления) вопрос об устойчивости полученного равновесия, т.е., иными словами, о том является ли полученная стационарная точка точкой минимума для потенциала. Пока отложим ответ на этот вопрос, заметив — исключительно из соображений исторического сюрприза, что теория управления возникла из задачи, которую сформулировал в 1868 г. один ученый, фамилию которого наблюдательный читатель настоящего раздела легко угадает! Намек: Эдвард Раус (Edward John Routh) — один из авторов критерия Рауса-Гурвица — был однокурсником этого ученого.

Для случая $ L=1 $ стационарная точка потенциала (Ферма-Торричелли) единственна для каждого фиксированного набора значений весов. Решение обратной задачи тоже было единственным — с точностью до домножения вектора весов $ (m_1^{ast},m_2^{ast},m_3^{ast} ) $ на сомножитель. Для других показателей $ L_{} $ стационарных точек у соответствующих потенциалов может быть несколько. Примером может являться случай кулоновского потенциала $ L=-1 $. Наряду с точкой $ P_{ast} $, гарантированной условием теоремы, будет существовать еще, по крайней мере, одна «посторонняя» стационарная точка $ tilde P_{ast} $. Следовательно, решение обратной задачи определяется не единственным образом: существует набор весов $ (widetilde{m}_1^{ast},widetilde{m}_2^{ast},widetilde{m}_3^{ast}) $, обеспечивающий стационарность точки $ tilde P_{ast} $ и непропорциональный набору $ (m_1^{ast},m_2^{ast},m_3^{ast}) $.

Результат предыдущей теоремы позволяет существенно упростить решение «прямой» задачи.

Т

Теорема [12, 13].Обозначим

$$
S_1(x,y)=
left|
begin{array}{ccc}
1 & 1 & 1 \
x & x_2 & x_3 \
y & y_2 & y_3
end{array}
right|,
S_2(x,y)=
left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x & x_3 \
y_1 & y & y_3
end{array}
right|,
S_3(x,y)=
left|
begin{array}{ccc}
1 & 1 & 1 \
x_1 & x_2 & x \
y_1 & y_2 & y
end{array}
right| , .
$$
Любое решение системы
$$ partial F / partial x = 0, partial F / partial y = 0 , $$
отличное от $ { P_j } $, удовлетворяет соотношению
$$
m_1:m_2:m_3=|PP_1|^{2-L} S_1(x,y):|PP_2|^{2-L} S_2(x,y):|PP_3|^{2-L} S_3(x,y) .
$$
В случае, когда $ L_{} $ четно, вторая система ни чем не лучше первой: степени получающихся алгебраических уравнений одинаковы. Но вот в случае, когда $ L_{} $ — нечетно (как в случае кулоновского потенциала), преимущество второй системы становится очевидным: избавиться от радикалов можно однократным возведением в квадрат.

=>

Для нечетных значений $ Lin mathbb Z $ стационарные точки функции $ F_{} $ удовлетворяют системе алгебраических уравнений

$$
left{ begin{array}{ll}
m_2^2S_1^2(x,y) |PP_1|^{2(2-L)} — m_1^2S_2^2(x,y) |PP_2|^{2(2-L)} & =0, \
m_2^2S_3^2(x,y) |PP_3|^{2(2-L)} — m_3^2S_2^2(x,y) |PP_2|^{2(2-L)} & =0.
end{array}
right.
$$

П

Пример. В рассмотренном выше примере функции

$$
F(x,y)=frac{1}{sqrt{(x-1)^2+(y-1)^2}}+ frac{m_2}{sqrt{(x-5)^2+(y-1)^2}}+frac{m_3}{sqrt{(x-2)^2+(y-6)^2}}
$$
предложенный алгоритм приводит к системе
$$
widetilde F_1(x,y,m_2,m_3)=0, widetilde F_2(x,y,m_2,m_3)=0 ,
$$
при
$$
begin{array}{c}
widetilde F_1(x,y,m_2,m_3)= \
=m_2^2,(5,x+3,y-28)^2(x^2+y^2-2,x-2,y+2)^3 -(5,x-y-4)^2(x^2+y^2-10,x-2,y+26)^3 , \
widetilde F_2(x,y,m_2,m_3)= \
=m_2^2,(4,y-4)^2(x^2+y^2-4,x-12,y+40)^3 -m_3^2,(5,x-y-4)^2(x^2+y^2-10,x-2,y+26)^3.
end{array}
$$
Здесь $ deg widetilde F_1 = deg widetilde F_2 =8 $ относительно переменных $ x_{} $ и $ y_{} $; это можно считать существенным успехом в сравнении с $ 28 $-й степенью уравнений, полученных в ходе первоначального решения.

Допустим, мы хотим исследовать динамику множества вещественных решений этой системы при различных фиксированных значениях $ m_2 $ и для произвольных значений $ m_3 $. Для получения неявного задания кривой
$$ H(x,y,m_2) = 0 , $$
которая будет состоять из решений системы при всевозможных значениях $ m_3 $, мы должны исключить этот параметр из системы. Но он, фактически, уже исключен: первое уравнение от него не зависит! Иными словами, утверждается, что уравнение
$$ m_2^2,(5,x+3,y-28)^2(x^2+y^2-2,x-2,y+2)^3 -(5,x-y-4)^2(x^2+y^2-10,x-2,y+26)^3=0 $$
при каждом фиксированном значении $ m_{2}=m_{2ast} $ определяет на плоскости $ (x,y) $ кривую, целиком состоящую из стационарных точек семейства кулоновских потенциалов
$$ left{ frac{1}{sqrt{(x-1)^2+(y-1)^2}}+ frac{m_{2ast}}{sqrt{(x-5)^2+(y-1)^2}}+frac{m_3}{sqrt{(x-2)^2+(y-6)^2}} right}_{m_3 in mathbb R} . $$
Изобразим несколько таких кривых на рисунке (числа на кривых обозначают величины $ m_2 $; ветви одинакового цвета соответствуют одинаковым значениям этого заряда).

♦

§

Более подробное исследование этой задачи

☞

ЗДЕСЬ.

При составлении настоящего раздела существенно использовалось содержание обзорной статьи

[*]

. Martini H. Fermat-Torricelli problem. Encyclopedia of Mathematics. Supplement III. Kluwer Academic Publishers. 2001, C.149-151

[1]. Weber A. Über den Standort der Industrien. Teil I: Reine Theorie des Standorts. J.C.B.Mohr, 1909. Tübingen.

Вебер А. Теория размещения промышленности. М.-Л. «Книга». 1926. (На самом деле, последняя книга — не перевод оригинальной книги Вебера, а изложение ее содержания переводчиком Н.Морозовым¹²⁾).

[2]. Дингельдэй Фр. Сборникъ задачъ по приложенiю дифференцiальнаго и интегральнаго исчисленiй. С.-Петербург. 1912

[3]. Курант Р., Роббинс Г. Что такое математика? М.МЦНМО. 2004

[4]. Протасов В.Ю. Максимумы и минимумы в геометрии. М.МЦНМО. 2005

[5]. Уланов Е.А., Утешев А.Ю. Аналитическое решение обобщенной задачи Ферма-Торричелли-Штейнера./ / Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2011. С. 201–206.

[6]. Launhardt W. Kommercielle Tracirung der Verkehrswege. Zeitschrift f. Architekten u.Ingenieur-Vereinis im Königreich Hannover. V. 18, pp. 516-534, 1872. Текст

☞

ЗДЕСЬ.

[7]. Maxwell J.C. Paper on the Description of Oval Curves. Observations on Circumscribed Figures Having a Plurality of Foci, and Radii of Various Proportions. 1846.
«The Scientific Letters and Papers of James Clerk Maxwell: 1846-1862» Vol. 1, Cambridge University Press. 1990

[8]. Maxwell J.C. A Treatise on Electricity and Magnetism. Vol. 1. Dower, New York. 1954

[9]. Maxwell J.C. On Governors. Proc. Royal Soc. London. 1868, V.16: pp. 270–283.

[10]. Sturm R. Über die Punkte kleinster Entfernungssumme von gegebenen Punkten. J. Reine Angew. Math., V. 97, pp.49-61, 1884.

[11]. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer.Math.Monthly. V. 121, N 4, pp.318-331, 2014. Текст

☞

ЗДЕСЬ (pdf).

[12]. Uteshev A.Yu., Yashina M.V. Stationary Points for the Family of Fermat-Torricelli-Coulomb-like potential functions. Proc. 15th Workshop CASC (Computer Algebra in Scientific Computing), Berlin 2013. Springer. Lecture Notes in Computer Science. V.8136 pp. 412-426,
2013.

[13]. Uteshev A.Yu., Yashina M.V. On Maxwell’s Conjecture for Coulomb Potential Generated by Point Charges. Springer. Transactions on Computational Sciences XXVII. Lecture Notes in Computer Science. V. 9570, pp. 68-80, 2016. Текст

☞

ЗДЕСЬ (pdf)

[14]. Weiszfeld E. Sur le point pour lequel la somme des distances de $ n_{} $ points donnés est minimum. Tohoku Math. Journal. V. 43, pp. 355–386, 1937.

[15]. Gabrielov A., Novikov D., Shapiro B. Mystery of Point Charges. Proc. London Math. Soc. Ser. 3. V. 95, pp. 443-472, 2007.