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


§

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

\begin{array}{c} P_1 \\ m_1 \end{array} ; \dots ; \begin{array}{c} P_K \\ m_K \end{array}

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 ... 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

\begin{array}{c} P_{1}=(2,6), \\ m_{1}=2 \end{array}\ ; \ \begin{array}{c} P_{2}=(1,1), \\ m_{2}=3 \end{array} \ ; \ \begin{array}{c} P_{3}=(5,1), \\ m_{3}=4 \end{array} \ .

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

\begin{array}{c} P_{1}=(2,6) \\ m_{1}=2 \end{array}\ ; \ \begin{array}{c} P_{2}=(1,1) \\ m_{2}=3 \end{array} \ ; \ \begin{array}{c} P_{3}=(5,1) \\ m_{3}=4 \end{array}

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

\begin{array}{c} P_{1}=(1,1) \\ m_{1}=1 \end{array}\ ; \ \begin{array}{c} P_{2}=(3,5) \\ m_{2}=1 \end{array} \ ; \ \begin{array}{c} P_{3}=(7,2) \\ m_{3}=1 \end{array} \ ; \ \begin{array}{c} P_{4}=(6,6) \\ m_{4}=m \end{array}

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} \displaystyle \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 \\ \displaystyle \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

\begin{array}{c} P_{1}=(1,1) \\ m_{1}=1 \end{array}\ ; \ \begin{array}{c} P_{2}=(3,5) \\ m_{2}=1 \end{array} \ ; \ \begin{array}{c} P_{3}=(7,2) \\ m_{3}=1 \end{array} \ ; \ \begin{array}{c} P_{4}=(6,6) \\ m_{4}=m \end{array}

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

\begin{array}{c} P_1 \\ m_1 \end{array} ; \dots ; \begin{array}{c} P_K \\ m_K \end{array}

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 proportinal 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 equlilibrium 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 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 28th 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 parametres (charges or masses) it it possible to guarantee the prescribed position of an equlibrium 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 the 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 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 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 vanishement 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. Springer. Transactions on Computational Sciences XXVII. Lecture Notes in Computer Science. V.9570, 2016, pp. 68-80.

[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 2017.
8) On excluding an extraneous factor

2018/05/14 17:53 редактировал au