Инструменты сайта


Русская версия


§

Satellite page for Distance evaluation between geometric objects


Fermat-Torricelli problem and its development

Generalized Fermat-Torricelli problem

Problem. Given the coordinates of $ K_{} $ points in $ \mathbb R^{n}_{} $ : $ \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^K $ and the real numbers $ \{ m_j \}_{j=1}^K $, find the coordinates of the point $ P_{\ast}=(x_{\ast 1},\dots,x_{\ast n}) $ solving the following optimization problem: $$ \min_{P\in \mathbb R^n} F(P) \qquad for \qquad F(P)= \sum_{j=1}^Km_j |PP_j| \ . $$ Here $ | \cdot | $ stands for the Euclidean metrics: $$ |P_1P_2|=\sqrt{(x_{11}-x_{21})^2+\dots+(x_{1n}-x_{2n})^2} \, . $$

§

The problem is known as the generalized Fermat-Torricelli problem, the Fermat-Torricelli-Steiner problem, the Weber problem, the weighted geometric median problem.

The values $ \{ m_j \}_{j=1}^K $ are generically taken positive. We will refer to them as weights while the sequence $$ \left\{ \begin{array}{l|c|l} P_1 & \dots & P_K \\ m_1 & \dots & m_K \end{array} \right\} $$ will be called configuration of weights.

Planar case

Consider first the planar case: $ 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} \ . $$

§

This problem is known as the problem of railway junction1), and, in case $ K=3 $, as three factory problem.

Ex

Example. The last two names were inspired by a facility location problem such as the following. Let the cities $ P_1,P_2, $ and $ P_3 $ be the sources of iron ore, coal, and water, respectively. To produce one ton of steel, the steel works need $ m_1 $ tons of iron, $ m_2 $ tons of coal, and $ m_3 $ tons of water. Assuming that the freight charge for a ton-kilometer is independent of the nature of the cargo, find the optimal position for the steel works connected with $ P_1,P_2 $, and $ P_3 $ via straight roads so as to minimize the transportation costs.

§

Since the end of the 19th century similar problems have became the subject of investigation in Economic Geography. Systematic exploration was started by Wilhelm Launhardt

Sind lediglich zwei Orte durch eineb Verkehrsweg zu verbinden, so ist die kommercielle Trace offenbar eine beide Orte verbindende gerade Linie.

Liegt aber feitlich dieser Verbindugslinie ein dritter Ort $ C_{} $, welche mit den ersten beiden Orten $ A_{} $ und $ B_{} $ in Verkehr zu leßen ist, so find außer der Trace $ AB $ auch die beiden Tracen $ AC $ und $ BC $ erwünscht, also alle drei Seiten des Dreiecks $ ABC $. Es würde dadurch am vortheilhaftesten gesorgt sein, so lange man den Verkehr zwischen je zweien der Otre unabhängig von dem Gesammtverkehre auffaßt; allein es ist in Frage zu ziehen, ob man nicht den Verkehr des dritten Ortes, statt von demselben direct auf jeden der andern beiden Orte $ A_{} $ und $ B_{} $ zu bauen, besser mittelst eienes Zweiges $ CO $ an irgend einen Punkt $ O $ der Verbindugslinie $ AB $ anschließen un zu dem Zwecke die durchgebende Linie $ AB $ in gebrochener Form $ AOB $ dem Orte $ C $ etwas nähern könnte. Ehe man die Frage entscheiden kann, ob überhaupt die Anlage eines solchen Knottenpunktes $ O $ sich empfiehlt, ist zu untersuchen, welches die günstigste Lage des Knottenpunktes ist. Diese Aufgabe bildet das ``Problem des Knotenpunktes''. [3]

and later carried on by Alfred Weber

If weight and distance are the only two determining factors, evidently transportation costs will draw industrial production to those places where the fewest ton-miles originate during the entire process of production and distribution; for with production at these places the cost of transportation will be lowest.

But how will the places of minimum ton-miles actually distribute the production? That is the real question to be answered.

In order to answer it, the simplifying assumptions of the whole theory set forth… We are to regard as given the location and the size of the places of consumption of each kind of production; and we are to regard as given the location of the available material deposits. Furthermore … we proceed upon the assumption that each product will be produced in one stage of production, the raw material being turned into the finished product at some single place of production.

Let us imagine ourselves stationed at some one of these given places of a given amount of consumption. Clearly, viewed from this place, there must be for every kind of product consumed at this place deposits of materials (raw materials, power materials) the use of which will result in the lowest transportation costs.

By no means will these deposits necessarily be those located nearest to the place of consumption. It is possible that in the case of certain materials a position near deposits is more important … than a position near place of consumption. In such a case that position will be chosen that is optimal… The location of the place of production must be determined somehow in some relationship to the place of consumption and to these most advantegeously located material deposits. Thus «locational figures» are created, one for each place of consumption of each product…

Let us suppose, for example, that we are dealing with a product composed of two materials we are to be found in scattered deposits. In such a case the «locational figures» would be represented by triangles…

Let us imagine a process of production which uses two localized materials, three-fourths of a ton of the one and one-half ton of the other being necessary to produce one ton of the product. The locational figure shows the weights three-fourths and one-half moving along these components of the two materials; while the component of consumption carries the weight one. [12].

In the 20th century these problems form a branch of Operations Research known as Facility Location Problem or Location Theory (Location Analysis).

The particular case of the problem corresponding to $ n=2 , K=3 $ and $ m_1=m_2=m_3=1 $ is known as the (classical) Fermat-Torricelli problem: for three given noncollinear points $ P_1=(x_1,y_1), P_2= (x_2,y_2) $ and $ P_3= (x_3,y_3) $ find $$ \min_{(x,y)} F(x,y) \qquad for \qquad 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.

Let us now consider several approaches for this problem. To find the coordinates of the stationary point $ P_{\ast}=(x_{\ast},y_{\ast}) $ compose the gradient system of equations: $$ \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. $$ This system is nonlinear and even non-algebraic with respect to $ x_{} $ and $ y_{} $. Therefore the problem of establishing its consistency and evaluation of the number of its real solutions is solved via specific algorithms.

Mechanical solution

Denote $$ \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 , $$ where $ \gamma_j $ stands for the angle made by $ \vec{PP_{j}} $ with the $ x_{} $-axis. Then the equations of the system can be rewritten as: $$ \left\{ \begin{array}{ll} m_1\cos \gamma_1 + m_2 \cos \gamma_2 + \dots + m_K\cos \gamma_K &=0,\\ m_1\sin \gamma_1 + m_2 \sin \gamma_2 + \dots + m_K \sin \gamma_K &=0 . \end{array} \right. $$ If $ m_{j} $ is treated as the force value applied at $ P_{} $ and oriented at $ P_{j} $, then the obtained equations mean that the sum of projections of all the applied forces to the coordinate axes equals zero, i.e. at the point $ P_{\ast} $ these forces provide an equilibrium. These arguments lie in the base of the following mechanical model2): a horizontal board is drilled with holes at the points $ \{P_j\} $ (or at the vertices of a polygon similar to $ P_1 P_2 \ldots P_K $). Strings are tied together in a knot at one end, the loose ends are passed through the holes and are attached to physical weights proportional to $ \{m_j\} $ respectively below the board. The equilibrium position of the knot yields the solution point $ P_{\ast} $.

It is intuitively evident that if the weight through the hole $ P_{i} $ overloads much the sum of remaind loads, then the knot will be sucked into this hole. It turns out that, on increasing the weight $ m_{i} $, this will happened before the fulfillment of the condition $ m_i = \displaystyle \sum_{j\ne i} m_j $. V. HERE.

Geometrical solution

It is known for the case of $ K=3 $ points for arbitrary values of the weights $ \{ m_j \} $ and for the equal weighted case of $ K=4 $ points.

Historically the first known solution was suggested by Torricelli not later than 16403) for the case of $ K=3 $ points and equal weights $ m_1=m_2=m_3=1 $ (the classical Fermat-Torricelli problem). The procedure for finding $ P_{\ast} $ lied within the classical geometry paradigma, i.e. with the aid of (solely) circinus et regula. The circles circumscribing the equilateral triangles constructed on the sides of and outside the triangle $ P_{1}P_2P_3 $ intersect at the point $ P_{\ast} $. The figure illustrates the construction for $ P_{\ast} $ for the choice $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $. Since that time, several extra algorithms have been suggested. Thus, for instance, the point $ P_{\ast} $ can be found as the point of intersection of lines $ T_1 P_2 $ and $ T_2 P_1 $ .

This solution is generalized in [2,3] for the case of distinct weights. Consider the system of equations from the previous section: $$ \left\{ \begin{array}{ll} m_1\cos \gamma_1 + m_2 \cos \gamma_2 + m_3\cos \gamma_3 &=0,\\ m_1\sin \gamma_1 + m_2 \sin \gamma_2 + m_3 \sin \gamma_3&=0 . \end{array} \right. $$ Resolve these equations with respect to $ \cos \gamma_1 $ and $ \sin \gamma_1 $ and substitute into equality $$ \begin{array}{ll} 1=\cos^2 \gamma_1+ \sin^2 \gamma_1 & \displaystyle = \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 = \\ & = \displaystyle \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) \ . \end{array} $$ Note that the natural restriction for the problem statement is $ |\cos (\gamma_2 -\gamma_3)| \le 1 $, i.e. $ m_1\le m_2+m_{3} $ (any of the weights does not exceed the sum of the other weights; as a matter of fact, the condition that the point $ P_{\ast} $ being searched is dictinct from $ P_1,P_2,P_3 $, turns out to be more stiff — v. BELOW). Next, from the last equality follows that: $$ \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} \ . $$ Similar relationships are valid for the sines of another pairs of angles. Wherefrom one gets a condition to be fulfilled for the point $ 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} \ . $$ Geometrical sense of the difference $ \gamma_1 -\gamma_2 $ is clarified by the figure: this is the value of the angle $ \widehat{P_1 P_{\ast}P_2} $.

For the case $ m_1=m_2=m_3=1 $, the last equality describes the point inside the triangle known as the Fermat-Torricelli point: this is the point making the angle $ 2\, \pi/3 $ with any two vertices. This point not always exists — it can be found only for the triangles with the angles less than $ 2\, \pi/3 $.

Th

Theorem [1]. The Fermat-Torricelli point exists only fot the triangle $ P_{1}P_2P_3 $ with the angles $ < 2\pi/3 $. In this case it is unique and is the point of the (global) minimum for $ |PP_1|+|PP_2|+|PP_3| $. If any of the angles of the triangle is $ \ge 2\pi/3 $, then the $ \min ( |PP_1|+|PP_2|+|PP_3| ) $ is attained when $ P_{} $ is placed into the corresponding vertex.

Ex

Example. For the points

$$ P_1=(1,1),\ P_2=(3,5),\ P_3= (7,2) $$ the Fermat-Torricelli point is shown in the figure (exact coordinates BELOW).


Consider now the general case of not necessarily equal weights. Construct the triangle $ P_2P_3Q $ with the lengths of the sides given by $$ |P_3Q|=\frac{m_2}{m_1}|P_2P_3|,\ |P_2Q|=\frac{m_3}{m_1}|P_2P_3| \ , $$ lying outer with respect to the triangle $ P_{1}P_2P_3 $. This triangle is similar to the so-called weight triangle, i.e. to the triangle composed from the sides formally coinciding with the values of the weights $ m_1,m_2,m_3 $.

The line $ QP_1 $ intersects the circumferences drawn through the points $ P_2,P_3 $ and $ Q $ in the point $ P_{\ast} $ being searched. Indeed, (v. the figure below), by the law of sines for the triangle $ P_2P_3Q $, the following equalities are fulfilled: $$ \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} \ . $$ By construction of $ P_{\ast} $, the following relationships are valid: $$ \mu_1+\nu_1=\mu_2+\nu_2= \mu_3+\nu_3= \pi \ , $$ and, consequently, the restrictions for the angles $ \mu_1, \mu_2, \mu_3 $ are the same as those for $ |\gamma_3-\gamma_2 |, |\gamma_3-\gamma_1 |, |\gamma_2-\gamma_1 | $.

Minimal value for $ F_{}(x,y) $ is then equal to $ m_1 |P_1Q| $. The above mentioned arguments are valid under the additional condition that the point $ P_{\ast} $ lies inside the triangle $ P_{1}P_2P_3 $. Otherwise, the solution to the problem is attained in one of the points $ \{P_j\} $.

Ex

Example. Find the point $ P_{\ast} $ for the configuration

$$ \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\} \, . $$

Solution. Here $ |P_2P_3|=4 $ and, consequently, $ |P_2Q|=4 \cdot 2 = 8, |P_3Q|=4 \cdot 3/2 = 6 $. These conditions fully identify the point $ Q_{} $ — as the one of the two points of intersection of the circumferences (centered in $ P_{2} $ of the radius $ 8_{} $ and centered in $ P_3 $ of the radius $ 6_{} $).

Its coordinates are $ \approx (6.5,-4.8) $. Draw the circumference through $ P_2,P_3,Q $. The line $ QP_1 $ intersects it in the point $ P_{\ast} \approx (3.9, 1.4) $ we are looking for, with the minimal value of the minimized function: $ F(x_{\ast},y_{\ast}) \approx 23.4 $.

Exact values for coordinates can be found BELOW.


For the case of $ K=4 $ points in the plane the geometrical solution is known only for the equal weighted case.

Th

Theorem [Fagnano] [2]. If the points $ P_{1},P_2,P_3, P_{4} $ make a convex quadrilateral, then

$$ \min( |PP_1|+|PP_2|+|PP_3|+|PP_4|) $$ is attained at the point $ P_{\ast} $of the diagonal intersection. Otherwise the minimum is attained at the point lying inside the triangle formed by the other three points.

Fermat-Torricelli point coordinates

Let $ \{P_j= (x_{j},y_j)\}_{j=1}^3 $. Denote $$ r_{j\ell}=\sqrt{(x_j-x_{\ell})^2+(y_j-y_{\ell})^2}=|P_jP_{\ell}| \quad for \ \{j,\ell\} \subset \{1,2,3\} \ . $$

Th

Theorem [8]. Let all the angles of the triangle $ P_{1}P_2P_3 $ be less than $ 2\pi /3 $, or, equivalently,

$$ 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 \ . $$ The coordinates of the Fermat-Torricelli point $ P_{\ast} $ are as follows $$ x_{\ast}=\frac{\kappa_1\kappa_2\kappa_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_1\kappa_2\kappa_3}{2 \sqrt{3} |S| d} \left(\frac{y_1}{\kappa_1}+\frac{y_2}{\kappa_2}+\frac{y_3}{\kappa_3} \right) $$ with $$ |P_1P_{\ast}|+|P_2P_{\ast}|+|P_3P_{\ast}|= \sqrt{d} \ . $$ Here $$ 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. $$ and $$ 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| \ . $$

§

If we represent the expressions for $ x_{\ast} $ and $ y_{\ast} $ symbolically as fractions in $ \{x_j,y_j\}_{j=1}^3 $, then it is possible to reduce their numerators and denominators by the common factor $ |S| $

Th

Тheorem. [8,9] Let all the angles of the triangle $ P_{1}P_2P_3 $ be less than $ 2\pi /3 $. The coordinates of the Fermat-Torricelli point $ P_{\ast} $ are as follows

$$ x_{\ast}=\frac{X}{2\sqrt{3}d}, \ y_{\ast}= \frac{Y}{2\sqrt{3}d} $$ with $$ |P_1P_{\ast}|+|P_2P_{\ast}|+|P_3P_{\ast}|= \sqrt{d} \ . $$ Here $$ 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{sgn} (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{sgn} (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)] \ ; $$ and $$ 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| \ . $$

§

$ |S|= 2 \times $ area of the triangle $ P_{1}P_2P_3 $.

Ex

Example. For $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ one gets:

$$ 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+22\sqrt{3}}\approx 8.8941 \ . $$ For $ P_1=(1,2),P_2=(3,3),P_3=(4,1) $ one gets: $$ 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 . $$

Check. The condition $$ \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} $$ is satisfied.

Analytical solution for the generalized Fermat-Torricelli problem

T

Theorem [8]. Denote the angle of the triangle $ P_{1}P_2P_3 $ at the vertex $ P_{j} $ as $ \alpha_j $. If the $ j $-th condition from the three following

$$ \ m_2^2+m_3^3+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\, , $$ is violated then the minimum of the function $$ F(x,y)=\sum_{j=1}^3 m_j \sqrt{(x-x_j)^2+(y-y_j)^2} $$ is attained at $ P_{j}=(x_j,y_j) $. If all the conditions are fulilled, then $ \min F(x,y) $ is attained at the point $ P_{\ast} $ with the coordinates: $$ 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), \quad 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) $$ with $$ F(x_{\ast},y_{\ast})=\min_{(x,y)\in \mathbb R^2} F(x,y)=\sqrt{d} \ . $$ Here $$ d=\frac{1}{2\sigma} (m_1^2K_1+m_2^2K_2+m_3^2K_3) $$ $$ = 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_{j\ell}=|P_jP_{\ell}|=\sqrt{(x_j-x_{\ell})^2+(y_j-y_{\ell})^2} \quad for \ \{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 \ , $$ $$ \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} \ , $$ and $$ \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. $$

Ex

Example. For the configuration

$$ \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\} $$ the point $ P_{\ast} $ has the coordinates

$$ x_{\ast}=\frac{1}{2866} \left( 4103+1833 \sqrt{15} \right)\approx 3.9086 , \ y_{\ast} =\frac{1}{8598} \left( 29523-4481 \sqrt{15} \right)\approx 1.4152 \ . $$ with $$ \min F(x,y)= m_1|P_{\ast}P_1|+m_2|P_{\ast}P_2|+m_3|P_{\ast}P_3|= 2\sqrt{79+15\sqrt{15}} \approx 23.4174 \ . $$

If we represent the expressions for $ x_{\ast} $ and $ y_{\ast} $ symbolically as fractions in $ \{x_j,y_j\}_{j=1}^3 $, then it is possible to reduce their numerators and denominators by the common factor $ |S| $. However, the final expressions look awful.

Analytical solution: elimination of variables

Results of the present section are essentially based on the content of the section Elimination of variables in a system of algebraic equations.

For the case of $ K>3 $ points, the complete analytical solution for the generalized Fermat-Torricelli problem can hardly be obtained. However, it is sensible to expand the analytics as far as possible. That means to reduce the problem of finding the coordinates of the stationary point $ P_{\ast} $ to solving an appropriate system of algebraic equations and further application of the elimination of variables procedure for this system.

Ex

Example. Establish the dynamics for the point $ P_{\ast} $ generated by the configuration

$$ \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\} $$ under the variation of the parameter $ m_{} $.

Solution. For any specialization of the parameter $ m_{} $ the coordinates of stationary point $ P_{\ast} $ can be evaluated via numerical methods; however, we are interested in any functional representation for $ P_{\ast} (m) $.

Let us transform the system of equations $$ \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. $$ to an algebraic one. This can be performed in different ways with the final result essentially depending on the utilized procedure, i.e., the algebraic system including the whole set of (complex!) solutions of the initial one is nonunique. We present only the final result of one of such procedures: $$ F_1(x,y,m)=0,\ F_2(x,y,m)=0 \ ; $$ here $ F_{1} $ and $ F_{2} $ are polynomials of degree $ 6_{} $ with respect to each of the variables $ x_{} $ or $ y_{} $ an the total degree $ 12_{} $ with respect to both variables. Via application of the resultant technique, it is possible to eliminate the variables $ x_{} $ or $ y_{} $ and deduce algebraic equations $$ \mathcal X(x,m)=0, \ \mathcal Y(y,m)=0, $$ giving the coordinates of stationary points for any specialization of $ m_{} $. It turns out, that their expressions can be simplified (by reducing of some extraneous factors) up the equations of the degree $ 12 $ with respect to each of the variables $ x_{} $ and $ y_{} $. The expression for $ \mathcal X(x,m) $ is HERE.

Further simplification is hardly possible since $ \mathcal X(x,m) $ and $ \mathcal Y(y,m) $ are irreducible over $ \mathbb Q_{} $, and, highly probably, are unsolvable in radicals.

An alternative approach consists in elimination of the parameter $ m_{} $ with the aid of finding the imlicit representation for the curve containing the stationary points for the whole family of the considered potential (i.e. for any value of $ m_{} $). The resultant $ \mathcal R_m(F_1,F_2) $ turns out to be the polynomial of the $ 96 $ degree in $ x_{} $ and $ y_{} $, and it can be factorized as $$ 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) \ . $$ The curve of stationary points is provided by a single factor, namely $$ \Phi(x,y) = 0 $$ where $$ \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 \ . $$ The complete expression for $ \Phi $ and the picture of the curve $ \Phi=0 $ are complicated; v. HERE. In the figure below we display only the branch corresponding to the true dynamics of the stationary point.

«Checkpoints» in this branch:

x $ \left(\frac{2}{687}(1029 + 79\sqrt{3}),\frac{1}{687}(1053 + 647\sqrt{3}) \right) $ — the Fermat-Torricelli point for the triangle $ P_1P_2P_{3} $, it corresponds to $ m=0 $;

x $ \left(\frac{29}{7},\frac{29}{7}\right) $ — the point of intersection of the diagonals of the quadrilateral $ P_1P_2P_3P_4 $, it corresponds to $ m_{}=1 $ (v. the Fagnano theorem);

$ (6,6) $ — the vertex $ P_{4} $, it corresponds to $ m \approx 2.4436 $ (the exact value is HERE);

$ (1,1) $ — the vertex $ P_{1} $, it corresponds to $ m \approx -2.4184 $ (as a matter of fact, the problem was initially stated for the positive values of weights; however, why not to implement the analytical coninuation? :-?);

x $ (\frac{11}{3},\frac{11}{3}) $, it corresponds to $ m=1-\sqrt{2/5} \approx 0.3675 $.

General case

Consider now the problem in $ \mathbb R^{n}_{} $. Stationary points of the function $$ F(P)= \sum_{j=1}^Km_j |PP_j| $$ are the real solutions of the gradient system of equations represented in the vector form as $$ \sum_{j=1}^K m_j\frac{P-P_j}{|PP_j|} = \mathbb O_{n\times 1} \ . $$ However, it should be taken into account that, firstly, for some configurations, this system might be inconsistent and, secondly, the function $ F_{}(P) $ may attain its maximal value at one of the points $ \{P_j\} $ (which does not monitored by this system).

Existence and uniqueness of solution

Th

Theorem. Let the points $ \{P_j\}_{j=1}^K \subset \mathbb R^n $ be distinct. Minimum of the function

$$ F(P)=\sum_{j=1}^K m_j |PP_j| $$ exists and is attained in a unique point.

1. If there exists a point $ P_{i} $ such that the inequality $$ \left|\sum_{j=1 \atop j \ne i}^K m_j \frac{P_j-P_i}{|P_jP_i|} \right| \le m_i \ , $$ is valid then $ \min F(P) $ is attained in $ P_{i} $;

2. if for any $ i \in \{1,\dots,K\} $ the condition $$ \left|\sum_{j=1 \atop j \ne i}^K m_j \frac{P_j-P_i}{|P_jP_i|} \right| > m_i \ , $$ is fulfilled then $ \min F(P) $ is attained in the point $ P_{\ast} $, satisfying the gradient system of equations $$ \sum_{j=1}^K m_j \frac{P-P_j}{|PP_j|}=\mathbb O_{n\times 1}\, ; $$ in this case $ P_{\ast} \not\in \{P_j\}_{j=1}^K $.

Ex

Example. Find the restrictions for the parameter $ m_{} $ under which the configuration

$$ \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\} $$ generates the minimum for $ \sum_{j=1}^4 m_j|PP_j| $ in the point $ P_4 $.

Solution. Form the condition 1 from the theorem: $$ \left| m_1 \frac{(1,1)- (6,6)}{\sqrt{50}}+m_2\frac{(3,5)- (6,6)}{\sqrt{10}}+m_3 \frac{(7,2)- (6,6)}{\sqrt{17}} \right| \le m_4 \ . $$ Answer. $ m \ge \sqrt{3+4/\sqrt{5}+3\sqrt{2/17}+\sqrt{2/85}} \approx 2.4436 $.

Notice that the point $ P_{\ast} $ get into the vertex $ P_{i} $ for the values of $ m_{i} $ lesser than the sum of remained weights.
=>

For the case $ n=2, K=3 $ the conditions of the theorem can be reformulated in terms of the angles $ \alpha_1,\alpha_2, \alpha_3 $ of the triangle $ P_1P_2P_{3} $. Thus, for instance, the condition 2 is equivalent to

$$ \ 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\, . $$ If $ m_1=m_2=m_3 $, then these conditions have the meaning that the angles of the triangle are less than $ 2\pi/3 $. For the general case these conditions can be supplied with the following geometric interpretation. Their fulfillment implies that treating the values of the weights $ m_1,m_2,m_3 $ as the lengths of the segments, one may construct a triangle from them. Denote the angles of the triangle by $ \beta_1, \beta_2, \beta_3 $ in accordance with the figure. Then, by the law of cosines, one gets: $$ \cos \alpha_j+ \cos \beta_j > 0 \quad for \quad j\in \{1,2,3\} \, . $$

Numerical solution

Consider first the equal weighted case $ m_1=\dots=m_K=1 $ in $ \mathbb R^{n}_{} $. Rewrite the gradient system of equations $$ \frac{P-P_1}{|PP_1|}+\dots+\frac{P-P_K}{|PP_K|}= \mathbb O_{n\times 1}, $$ giving the stationary points of the function $ F(P) $, in the equivalent form $$ 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)} \, . $$ Thus the problem is reduced to the one of finding the fixed point of the fuction $ \Phi(P) $. Let us find it via iteration method. Take as the initial guess an arbitrary point $ P^{(0)} \not\in \{P_j\}_{j=1}^K $ and construct the sequence recursively $$ P^{(k)}=\Phi(P^{(k-1)}) \quad for \quad k \in \mathbb N \ . $$ It is claimed that this sequence converges to the point $ P_{\ast} $ which yields the minimum value for $ F(P)=\sum_{j=1}^K |PP_j| $.

The method is known as the Weiszfeld algorithm [13].

Ex

Example. For $$ P_1=(1,1), P_2=(3,5), P_3=(7,2) $$

let us take $ P^{(0)}=(2,2) $. Iterative sequence $$ \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 $$ converges to the Fermat-Torricelli point $ P_{\ast}\approx (3.3939, 3.1639 ) $.

Ex

Example. For $$ P_1=(1,1,0), P_2=(5,1,0), P_3=(2,6,0), P_4=(3,3,5) $$

let us take $ P^{(0)}=(1,1,1) $. Iterative sequence $$ \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 $$ converges to the point $ P_{\ast} \approx (2.6823, 2.4298, 0.9607) $.

The convergence problem arises when the searched point $ P_{\ast} $ turns out to lie close to one of the configuration points $ \{P_j\}_{j=1}^K $.

Ex

Example. For

$$ P_1=(0,0), P_2=(1,0), P_3=(-4,7) $$ the Fermat-Torrricelli point $ P_{\ast}\approx (0.0023,0.0039) $. Iterative sequence with the initial guess $ P^{(0)}=(0,1) $ does not attain this accuracy within the $ 200 $ iterations.

The method is evidently generalized to the case of unequal weights: in the recursive formula one should take $$ \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) \ . $$

Inverse problem

Problem. Given the point $ P_{\ast} \in \mathbb R^n $, we wish to find the values for the weights $ \{m_j\}_{j=1}^{n+1} $ with the aim for the corresponding objective function $ \sum_{j=1}^{n+1} m_j |PP_j|^L $ to posses a minimum point precisely at $ P_{\ast} $.

Although this problem looks like an equivalent in complexity to the direct one, it admits a surprisingly simple solution. We will first treat the planar case: $ n=2, K=3 $.

Th

Theorem [7]. Let the vertices of the triangle $ P_1P_2P_3 $ be counted counterclockwise. Then for the choice

$$ 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| $$ the function $$ F(x,y) = \sum_{j=1}^3 m_{j}^{\ast} \sqrt{(x-x_j)^2+(y-y_j)^2} $$ has its stationary point at $ P_{\ast} $. Provided that the latter is chosen inside the triangle $ P_1P_2P_3 $ the values $ m_1^{\ast},m_2^{\ast},m_3^{\ast} $ are all positive and $$ 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| \ . $$

Proof of the theorem together with the geometrical meaning for the values from its formulation is HERE.

Solution of the inverse problem is determined up to a common positive multiplier, i.e. the solution triple $ (m_1,m_2,m_3) $ is defined by the value of the ratio $ m_1 : m_2 : m_3 $. Up to this remark4), solution of the inverse problem is unique.
Ex

Example. Place the corresponding weights $ \{m_j^{\ast}\} $ in the points

$$ P_{1}=(2,6),P_{2}=(1,1), P_{3}=(5,1) $$ for the function $ F(x,y) $ to get the minimum point at $$ P_{\ast} = \left(\frac{ 4103+1833 \sqrt{15}}{2866} ,\ \frac{29523-4481 \sqrt{15}}{8598} \right) \ . $$

Solution. Formulas from the theorem yield: $$ \left\{\begin{array}{ccl} m_1^{\ast}&=& \displaystyle \frac{2(20925-4481\sqrt{15})}{18481401}\sqrt{316380606+35999826\sqrt{15}} \ ,\\ m_2^{\ast}&=& \displaystyle \frac{2(15105-2342\sqrt{15})}{6160467}\sqrt{75400161-9169767\sqrt{15}} \ , \\ m_3^{\ast}&=& \displaystyle \frac{8(-1185+15988\sqrt{15})}{18481401}\sqrt{8335761-2050623\sqrt{15}}\ , \end{array} \right. $$ with $$ F(x_{\ast},y_{\ast})=\frac{1}{4299}(-333980+193436\sqrt{15}) \ . $$ Compare this result with the one presented in ABOVE. In accordance with the previous remark, the following ratio $$ m_1^{\ast} : m_2^{\ast} : m_3^{\ast} = 2 : 3 : 4 $$ should be valid. Are you able to believe?

§

Generalization of the result to multidimensional case $ n>2 $ for the number of points $ K=n+1 $ is HERE.

Adjacent problems

Steiner tree

Problem. Given set of points $ \mathbb P= \{P_j\}_{j=1}^K $ in the Euclidean plane, find a system of line segments such that their union forms a connected set $ \mathbb U $ containing $ \mathbb P $, and such that the total length of the line segments is minimized.

This problem of construction the shortest possible network interconnecting the points of the set $ \mathbb P $ is known as the (Euclidean) Steiner minimal tree problem.

The stated problem in its particular case of $ K=3 $ noncollinear points coincides with Fermat-Torricelli problem. It has a unique solution which

  • either coincides with the system of three segments connecting the points $ P_1,P_2,P_3 $ with the Fermat-Torricelli point of the triangle $ P_1P_2P_3 $; this is the case where every angle of the triangle $ P_1P_2P_3 $ is less than $ 2\pi/3 $;
  • or, in case where there exists a vertex $ P_j $ with the triangle angle equal to or greater than $ 2\pi/3 $, it coincides with the system of two triangle sides meeting at $ P_j $.

The case of $ n>3 $ points is much harder in treatment. It turns out that the Sreiner minimal tree problem should be distinguished from the Fermat-Torricelli problem.

Ex

Example. Find Steiner minimal tree for the points $$ P_1=(0,3),\ P_2=(0,0),\ P_3=(4,0),\ P_4=(4,3) \, . $$

Solution. Let us attempt to solve this problem on introducing successively extra points. At the first step, we do not add such points and use only the segments connecting the nearest points. In this case the solution of the problem is the polygonal chain $ P_1P_2P_3P_4 $ of the total length $ 3+4+3=10 $.

If it is allowed to introduce one extra point, then, according with the Fagnano result, it should be placed into the intersection of the diagonals of the rectangular:

However, the obtained configuration of the tree does not provide the shortage of the length: $ 5+5=10 $. In the next trial, let us intoduce two extra points locating them at $ P_{\ast}=\left(\frac{\sqrt{3}}{2},\frac{3}{2} \right) $ and $ P_{\ast \ast}=\left(4-\frac{\sqrt{3}}{2},\frac{3}{2} \right) $ and connecting them to the points $ \{P_j\}_{j=1}^4 $ with the following segment configuration:

Now the total length equals $ 4+ 3\sqrt{3} \approx 9.196152 $.

Is it possible to improve this result on introducing some extra points? The answer is negative: for any configuration of points $ \{P_j\}_{j=1}^4 $, the number of extra points needed to compose Steiner minimal tree never exceeds $ 2_{} $.

In the just tackled example, the point $ P_{\ast} $ is the Fermat-Torricelli point for the triangle $ P_1 P_2 P_{\ast \ast} $ while $ P_{\ast \ast} $ is the Fermat-Torricelli point for the triangle $ P_3 P_4 P_{\ast } $. This property turns out to be the principal one for the solution of the general problem: for any configuration of the points $ \{ P_j \}_{j=1}^K \subset R^2 $, the Steiner minimal tree is a graph connecting these points with auxiliary points from a certain set $ \{ S_{\ell} \}_{\ell=1}^M $. The cardinality of the latter is within the following ranges $$ 0 \le M \le K-2 $$ and, provided that it is nonempty, any of its entries is the Fermat-Torricelli point for some triple of points from the union $ \{ P_j \}_{j=1}^K \bigcup \{ S_{\ell} \}_{\ell=1}^M $. The degree of any vertex $ \{ P_j \}_{j=1}^K $ of the graph is either $ 1_{} $ or $ 2_{} $.

Multifocal ellipses

For the case $ n=2_{} $, consider the problem of drawing the level curves of the function $$ F(x,y)= \sum_{j=1}^{K} \sqrt{(x-x_j)^2+(y-y_j)^2} \ , $$ i.e. the curves $ F(x,y)=c $ for disctinct values of $ c_{} $. For $ K=2 $ solution to the problem is well-known — this is either an ellipse with the foci at $ P_1=(x_1,y_1),P_2=(x_2,y_2) $, or the segment $ P_1P_2 $, or the empty set (imaginary ellipse). What geometry corresponds to the case $ K \ge 3 $? What is, for instance, the locus of set of points the sum of distances from which to the fixed points $ P_1,P_2,P_3 $ is a constant? This question was posed by Descartes to Fermat at 1638 (and this was the starting point for the Fermat question on the minimum value of $ F_{} $).

These curves are known as multifocal ellipses,polyellipses or generalized ellipses. In German, they are known as Tschirnhaus'sche Eikurve (v. the figure below); thus, one American author translated this wittily as egglipse. The generalized ellipses can be treated as the algebraic curves: succesive squaring their equations permits one to eliminate the radicals.

Ex

Example. For $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ the family of trifocal ellipses (algebraic curves of the order $ 8_{} $) is displayed in the following figure (numbers in the curves display the corresponding values of the constant $ c_{} $):

What values of $ c_{} $ correspond to the curves passing through $ P_1, P_2, P_3 $ ?

For the general case of not necessarily equal $ \{ m_j \} $, the level curves of the function $$ F(x,y)= \sum_{j=1}^{K} m_j\sqrt{(x-x_j)^2+(y-y_j)^2} $$ have not got an approved name. For $ K=2 $, they are sometimes referred to as the Descartes ovals. If $ K\ge 3 $ and the values $ \{ m_j \} $ are (rationally) commensurable, then this case can be treated as an extreme case of the multifocal ellipse — when some of the foci stick together. In the mid 19th centrury, these curves attract5) the attention of one Scottish scholar [4]. For $ K=3 $, these curves are known in Economic Geography as isodapanes 6). Every such a curve consists of points of equal transportation cost to them from the given point $ \{P_j\} $.

A

Animation of the 3D analogue of the 4-foci ellipse HERE (470 Kb).

The triangular(optim)ization problems

Problem 1. Construct the maximal equilateral triangle $ Q_1Q_2Q_3 $ circumsribing the given triangle $ P_{1}P_{2}P_3 $ (any side of $ Q_{1}Q_{2}Q_3 $ must contain a vertex of $ P_1P_2P_3 $).

Th

Theorem. Let all the angles of the triangle $ P_{1}P_2P_3 $ be less than $ 2\pi /3 $. The altitude of $ Q_1Q_2Q_3 $ equals to $ |P_{\ast}P_1|+|P_{\ast}P_2|+|P_{\ast}P_3| $, where $ P_{\ast} $ stands for the Fermat-Torricelli point of the triangle $ P_{1}P_{2}P_3 $. The sides of the triangle $ Q_1Q_2Q_3 $ are normal to the lines $ P_{\ast}P_1, P_{\ast}P_2 $ and $ P_{\ast}P_3 $.

Problem 2. Construct the minimal equilateral triangle $ R_1R_2R_3 $ inscribed into the given triangle $ P_{1}P_{2}P_3 $ (any side of $ P_{1}P_{2}P_3 $ must contain a vertex of $ R_1R_2R_3 $).

For my surprise, I could not find the web resourses regarding the solution of Problem 2 except for THIS. The problem looks similar to the Fagnano's problem on the construction of arbitrary triangle of the least possible perimeter inscribed in the given acute one. However the restriction of equilateraty imposed on the triangle in the problem statement changes essentially the latter solution.

Th

Theorem. Let all the angles of the triangle $ P_{1}P_2P_3 $ be less than $ 2\pi /3 $. The sides of the triangle $ R_1R_2R_3 $ are normal to the sides of the triangle $ Q_1Q_2Q_3 $, from the solution of Problem 1. The following relationship is valid for the areas of the three triangles — the original, the minimal circumscribed and the maximal inscribed ones: $$ \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}} \ . $$

Stationary points for the family of potential functions

Problem. Find stationary points of the fuction $$ F(P)= \sum_{j=1}^K m_j \left|PP_j \right|^L \ . $$ Here $ \{P,P_1,\dots,P_K\} \subset \mathbb R^n $, $ L_{} $ is a real nonzero number, and $ \{ m_{j} \}_{j=1}^K \subset \mathbb R $ (thus, $ \{ m_{j} \} $ are not necessarily positive).

For the case $ L=1 $, one gets the generalized Fermat-Torricelli problem considered above. For the case $ L=2 $, the solution for the problem is a single point $$ P_{\ast}= \frac{\sum_{j=1}^K m_jP_j}{ \sum_{j=1}^K m_j} $$ which provides the global mimimum for $ F(P) $. For all positive $ \{m_j\}_{j=1}^K $ and $ n\in \{2,3\} $, the point $ P_{\ast} $ is the center of mass (barycenter) for the system of weights placed at the positions $ \{P_j\}_{j=1}^K $.

We are now interested in solution to the problem for other specializations of the exponent $ L_{} $. The stated problem can be given the physical interpretation. Treat the configuration $$ \left\{\begin{array}{c|c|c} P_1 & \dots & P_K \\ m_1 & \dots & m_K \end{array} \right\} $$ as a system of $ K_{} $ stationary fixed charged particles acting at a point unit charge placed at the position $ P_{} $; the acting force of the $ j_{} $th charge is directly proportional to the value of charge $ m_{j} $ and proportional to a power $ L_{} $ of the distance from this charge to the unit one. The problem consists in finding a point $ P_{\ast} \in \mathbb R^{n}_{} $, where the unit charge will be immovable, i.e. will be in the equilibrium position.

Of especial interest is a particular case of the problem, namely $ L=-1 $. This exponent corresponds to two physical potentials — Coulomb electrostatic and Newton gravitational.

Stationary points of this family are given by the system of equations $$ \left\{\frac{\partial F}{\partial x_{\ell}}= L \sum_{j=1}^{K} m_j |PP_j|^{L-1} \frac{(x_{\ell}-x_{j\ell})}{|PP_j|} = 0 \right\}_{\ell=1}^n \ , \quad \mbox{ for } \quad \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^K, P=(x_1,\dots,x_n) \ , $$ which is an algebraic one for even exponents $ L_{} $ (or can be immediately reduced to an algebraic one for negative $ L_{} $); for other specializations of $ L_{} $, it contains the radicals which can be eliminated on successive squaring of equations. For the Coulomb potential $ L=-1, n=2, K=3 $ this procedure results in algebraic equations of high degree with cumbersome coefficients.

Ex

Example. Let $$ P_1=(1,1), P_2=(5,1) , P_3=(2,6) \, . $$ Investigate the dynamics of the set of stationary points of the function

$$ F(x,y)=\frac{1}{(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}} $$ under variations of the parameters $ m_{2} $ and $ m_{3} $.

Solution. Gradient system of equations $$ \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} $$ can be transformed into an algebraic one with the aid of the following procedure. Denote by $ A_1, A_2 $ and $ A_3 $ the summands in any of these equations. Successive their squaring according with the scheme $$ 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 $$ results in an algebraic system $$ F_1(x,y,m_2,m_3)=0,\ F_2(x,y,m_2,m_3)=0 $$ where $ F_{1} $ и $ F_{2} $ denote the $ 28 $th degree polynomials in $ x_{} $ and $ y_{} $ with the coefficients up to the order $ 10^{19} $. Finding all the real solutions for this system — even for specialized (fixed) parameters $ m_2 $ and $ m_3 $ — is a hardly feasible task. Remind that the stated problem is even more complicated: the dynamics of the set of solutions has to be determined under the variations of the parameters!

The difficulty of the stated problem — compared with the generalized Fermat-Torricelly one — can also be estimated via mentioning the fact that the number of stationary points is greater than $ 1_{} $. This number variates from $ 2_{} $ to $ 4_{} $.

Conjecture [Maxwell] [5, 14]. The number of stationary points for the Coulomb field of any configuration of $ K_{} $ stationary charges in $ \mathbb R^3 $ never exceeds $ (K-1)^2 $.

Not proved7).

What does the problem stated have in common with the generalized Fermat-Torricelli problem? — It is the similarity in solving the inverse problem. Consider first the planar case.

Th

Theorem [10, 11]. Let the points $$ P_{1}=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3) $$ be noncollinear. Then for the choice

$$ 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| $$ the function $$ F(x,y) = \sum_{j=1}^3 m_{j}^{\ast} |PP_j|^L $$ possesses a stationary point at $ P_{\ast}=(x_{\ast},y_{\ast}) $. One has also $$ 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| \ . $$

Proof is similar to the one presented HERE.

We emphasize that, de facto, this result solves the Control Theory problem: via an appropriate selection of parameters (charges or masses) it possible to guarantee the prescribed position of an equilibrium for the potential field — either Coulomb's or Newton's one. The immediate next question concerns the stability property for the obtained equilibrium, or, in other words, whether or not the point provides the minimum value for the potential. The answer to this question will be postponed till a good time. Right now we mention only the surprising fact that the Control Theory — as a branch of Applied Mathematics — was born in 1868 from the problem posed by a scholar oftenly mentioned in the previous text, namely J.C.Maxwell [6].
For the case $ L=1 $, the stationary point of the potential (generalized Fermat-Torricelli) is unique for any specialization of weights. Solution of inverse problem is also unique — up to the scaling of the weight vector $ (m_1^{\ast},m_2^{\ast},m_3^{\ast} ) $. For another values of the exponent $ L_{} $, the corresponding potential might possess several stationary points. This statement can be exemplified via the Coulomb potential corresponding to $ L=-1 $. Aside with the point $ P_{\ast} $, guaranteed by the conditions of the theorem, there exists at least one extra stationary point $ \tilde P_{\ast} $. Consequently, the solution to the inverse problem is non-unique: there exists a vector of weights $ (\widetilde{m}_1^{\ast},\widetilde{m}_2^{\ast},\widetilde{m}_3^{\ast}) $, providing the stationary property for the point $ \tilde P_{\ast} $ and disproportional to the vector $ (m_1^{\ast},m_2^{\ast},m_3^{\ast}) $.

The result of the previous theorem simplifies the solution of the «direct» problem.

Th

Theorem [10, 11]. Denote

$$ 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| \, . $$ Any solution of the system $$ \partial F / \partial x = 0, \partial F / \partial y = 0 \ , $$ distinct from $ \{ P_j \} $, satisfies the relationships $$ 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) \ . $$ For the case of even values of $ L_{} $, the second system does not have any adwantage before the first one since the degrees of the obtained algebraic equations are equal. However, for the case of odd $ L_{} $ (like for the case of Coulomb potential), an advantage of the second system becomes evident: it is possible to get rid of the radicals via a single squaring.

=>

For $ L\in \mathbb Z $ the coordinates of stationary points of $ F_{} $ satisfy the following algebraic system $$ \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. $$

Ex

Example. For the function

$$ 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}} $$ treated in the above example, the suggested algorithm leads one to the system $$ \widetilde F_1(x,y,m_2,m_3)=0,\ \widetilde F_2(x,y,m_2,m_3)=0 \ , $$ with $$ \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} $$ Here $ \deg \widetilde F_1 = \deg \widetilde F_2 =8 $ with respect to the variables $ x_{} $ и $ y_{} $. This result should be treated as an essential success in comparison with the $ 28 $-th degree of equations obtained in the frame of the direct squaring approach. This time, it is realistic to eliminate any variable from the obtained algebraic system. For instance, the resultant of these polynomials treated with respect to $ x_{} $ $$ \mathcal Y(y,m_2,m_3)=\mathcal R_{x}(\tilde F_1,\tilde F_2) $$ is8) a polynomial of the degree $ 34 $ in $ y_{} $. Its complete expression is HERE. For any specialization of parameters $ m_2 $ and $ m_3 $, it is possible to find the exact number of real zeros and to localize them in the ideology of symbolic (analytical) computations (e.g., via the Sturm series construction). For instance, there are two stationary points $$ \mathfrak S_1 \approx (2.666216,\, 1.234430),\ \mathfrak S_2 \approx (2.744834,\, 3.244859) \quad \mbox{ for } \quad m_2=2, m_3=2 \ , $$ and four stationary points $$ \mathfrak S_1 \approx (1.941246,\, 2.552370) , \mathfrak S_2 \approx (2.655622,\, 1.638871) ,\ $$ $$ \mathfrak S_3 \approx (3.330794,\ 2.826444), $$ $$ \mathfrak N \approx (2.552939,\, 2.271691) \quad \mbox{ for } \quad m_2=2, m_3=4 \ . $$ The case of existence of exactly three stationary points for the Coulomb potential should be treated as an exceptional one, i.e. practically impossible for the randomly chosen parameters. The parameter restriction providing such an exception is of theoretical interest as a boundary between the two sets in the $ (m_2,m_3) $-plane, namely, the one containing the pairs of parameters providing exactly two stationary points for $ F_{} $ and another one corresponding to the case of exactly four stationary points. To obtain such a boundary, or, in other words the bifurcation values for the parameters, one should find the conditions for the alternation of the number of real zeros for $ \mathcal Y(y,m_2,m_3) $ treated as a polynomial with respect to $ y_{} $. For this aim, let us compute the discriminant of this polynomial $$ \mathcal D_y( \mathcal Y(y,m_2,m_3)) \ . $$ The result is a polynomial in $ m_2,m_3 $ which is factorized as: $$ \Xi^2(m_2,m_3) \Psi(m_2,m_3) \quad npu \quad \deg \Xi=444, \deg \Psi =48 \ . $$ Its vanishment is possible as a consequence of two different paces of developments. The condition $ \Xi(m_2,m_3)=0 $ relates to the scenario, when two distinct stationary points of $ F_{}(x,y) $ have the same $ y_{} $-coordinate. As for equation $$ \Psi(m_2,m_3)=0 \ , $$ it defines the discriminant curve in the $ (m_2,m_3) $-plane, the points in which correspond to the case of appearance of at least one degenerate stationary for point for $ F_{}(x,y) $. The complete expression for $ \Psi(m_2,m_3) $ is very cumbersome: its expansion consists of $ 325 $ terms (it is an even polynomial in its variables). We demonstrate here just only the terms of the highest and the lowest orders: $$ \Psi(m_2,m_3) $$ $$ =3^{36}(64\,m_3^2+192\,m_2m_3+169\,m_2^2)^5(64\,m_3^2-192\,m_2m_3+169\,m_2^2)^5 $$ $$ \times (28561\,m_2^4+19968\,m_2^2m_3^2+4096\,m_3^4)^7 $$ $$ + \dots $$ $$ + 2^2\cdot 3^{31} \cdot 17^{40} (5545037166327\, m_2^4-161882110764644\,m_2^2m_3^2+1656772227072\,m_3^4) $$ $$ + 2^3\cdot 3^{36}\cdot 17^{44} (51827\,m_2^2+28112\,m_3^2)+ 3^{36}\cdot 17^{48} \ . $$ Even the opportunity to compute such an expression should amazed as a miracle, however, the more surprising is the fact that it is possible to draw this curve. The figure can be found in the Russian page to be translated sometimes later; and here I present one of its points: $ m_2 \approx 1.842860, m_3 \approx 4.157140 $. The correspoding Coulomb potential $ F_{}(x,y) $ possesses the following stationary points $$ \hat{\mathfrak S}_1=(2.691693, 1.930238),\ \mathfrak S_2=(1.821563, 2.558877), $$ $$ \mathfrak S_3=(3.374990, 2.739157) \ ; $$ with $ \hat{\mathfrak S}_1 $ being the degenarate one of a saddle-node type.

§

The difference in notation of stationary points in the previous example — $ \mathfrak S $ vs. $ \mathfrak N $ — reflects their different topological character: the saddle type and the node type. In the latter case, the stationary point is the minimum point for the Coulomb potential.

References

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


[1]. Courant R., Robbins H. What is Mathematics? Oxford University Press, London, 1941.

[2]. Dingeldey F. Sammlung von Aufgaben zur Anwendung der Differenzial- und Integralrechnung. Zweiter Teil. Aufgaben zur Anwendung der Integralrechnung. Teubner. Leipzig. 1923

[3]. Launhardt W. Kommercielle Tracirung der Verkehrswege. Zeitschrift f. Architekten u.Ingenieur-Vereinis im Königreich Hannover. 18, 516-534, 1872.

[4]. 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

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

[6]. Maxwell J.C. On Governors. Proc. Royal Soc. London. 16, 270–283, 1868

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

[8]. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer.Math.Monthly. 121, N 4, 318-331, 2014. Text HERE (pdf)

[9]. Ulanov E.A., Uteshev A.Yu. Analytical solution for the generalized Fermat-Torricelli-Steiner problem. Control processes and stability: Proceedings of the 42th international scientific conference of graduates and postgraduates / A.S.Eriomin, N.V.Smirnov eds. St.Petersburg: St.Petersburg State University, 201–206, 2011. (in Russian).

[10]. 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. 8136, 412-426, 2013.

[11]. Uteshev A.Yu., Yashina M.V. On Maxwell’s Conjecture for Coulomb Potential Generated by Point Charges. Transactions on Computational Sciences XXVII. LNCS 9570, 2016, 68-80. Text HERE (pdf).

[12]. Weber A. Über den Standort der Industrie. Bd. 1: Reine Theorie des Standorts. 1909. Tübingen. English translation: The Theory of the Location of Industries, Chicago, Chicago University Press, 1929

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

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

1)
(Germ.) Problem des Knotenpunktes [2,3].
2)
Sometimes incorrectly called Pólya's mechanical model
3)
It is hypothesized that the problem posed by Fermat was transported to Italy by Mersenne.
4)
In the language of railway transportation, it is equivalent to the fact that the optimal position of junction is independent of the currency of the state: it does not matter whether in roubles or in dollars the freight charge is nominated.
5)
Just out of pure curiosity
6)
(An.Greek) $ \iota \sigma o \varsigma $ — equal, $ \delta \breve{\alpha} \pi \acute{\alpha} \nu \alpha $ — expenditure; the notion was introduced by A.Weber.
7)
As to 2020.
8)
On excluding an extraneous factor
matricese/optimize/distancee/torri_e.txt · Последние изменения: 2023/07/11 14:57 — au