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


§

Satellite page for Fermat-Torricelli problem and its development


Inverse problem for the Fermat-Torricelli problem

Problem. Find the values for the weights \{m_j\}_{j=1}^{K} with the aim for the corresponding objective function \sum_{j=1}^{K} m_j |PP_j| to posses a minimum point precisely at P_{\ast} \not\in \{P_j\}_{j=1}^K.

Planar case

Th

Theorem [3]. Let the vertices of the triangle P_{1}P_{2}P_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_{2}P_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. Substitute the values for the weights into the equations for partial derivatives for F_{}:

\left\{ \begin{array}{ll} \displaystyle \frac{\partial F}{\partial x} &= \displaystyle \frac{m_1^{\ast}(x_{\ast}-x_1)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+\frac{m_2^{\ast}(x_{\ast}-x_2)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+ \frac{m_3^{\ast}(x_{\ast}-x_3)}\sqrt{(x_{\ast}-x_3)^2+(y_{\ast}-y_3)^2}, \\ \displaystyle \frac{\partial F}{\partial y} &= \displaystyle \frac{m_1^{\ast}(y_{\ast}-y_1)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+\frac{m_2^{\ast}(y_{\ast}-y_2)}\sqrt{(x_{\ast}-x_1)^{2}+(y_{\ast}-y_1)^2}+ \frac{m_3^{\ast}(y_{\ast}-y_3)}\sqrt{(x_{\ast}-x_3)^2+(y_{\ast}-y_3)^2}. \end{array} \right.

We get

(x_{\ast}-x_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (x_{\ast}-x_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (x_{\ast}-x_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ ,
(y_{\ast}-y_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (y_{\ast}-y_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (y_{\ast}-y_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ .

In order to demonstrate that both of these expressions equal to 0_{}, let us utilize some properties of the determinant. Represent the first sum as the 4-th order determinant:

\left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ 0 & x_{\ast}-x_1 & x_{\ast}-x_2 & x_{\ast}-x_3 \end{array} \right|

Add now the second row to the last one:

\left| \begin{array}{llll} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast} & x_{\ast} & x_{\ast} & x_{\ast} \end{array} \right| \ .

In this determinant, the first row is proportional to the last one; therefore, the determinant equals just zero. The second equality can be verified in a similar manner.

Let us evaluate F(x_{\ast},y_{\ast}):

F(x_{\ast},y_{\ast}) =
= \left[(x_{\ast}-x_1)^2+(y_{\ast}-y_1)^2 \right] \left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right| + \left[(x_{\ast}-x_2)^2+(y_{\ast}-y_2)^2 \right] \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right| + \left[(x_{\ast}-x_3)^2+(y_{\ast}-y_3)^2 \right] \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ .

To prove the equivalence of this expression to the one from the statement of the theorem, let us split it into the x_{}-part and the y_{}-part. First, keep the x_{}-terms in brackets of the previous formula:

(x_{\ast}-x_1)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right| + (x_{\ast}-x_2)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right| + (x_{\ast}-x_3)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| \ .

Similar to the proof of the first part of the theorem, represent this linear combination as the 4-th order determinant as follows

\left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ 0 & (x_{\ast}-x_1)^2 & (x_{\ast}-x_2)^2 & (x_{\ast}-x_3)^2 \end{array} \right| \ .

Multiply the first row by (-x_{\ast}^2), the second one by 2\, x_{\ast} and add the obtained rows to the last one:

\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 & x_1^2 & x_2^2 & x_3^2 \end{array} \right| \ .

In exactly the same manner the equality

(y_{\ast}-y_1)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right| + (y_{\ast}-y_2)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right| +(y_{\ast}-y_3)^2 \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| = \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ y_{\ast}^2 & y_1^2 & y_2^2 & y_3^2 \end{array} \right|

can be proven. The linear property of determinant with respect to its rows completes the proof of the last statement of the theorem.

Geometrical meaning of the constants from the theorem

The value

\left| \begin{array}{ccc} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|

equals twice the area of the triangle P_{\ast} P_2P_3. The equalities

(x_{\ast}-x_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (x_{\ast}-x_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (x_{\ast}-x_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right|=0 \ ,
(y_{\ast}-y_1)\left| \begin{array}{lll} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|+ (y_{\ast}-y_2) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|+ (y_{\ast}-y_3) \left| \begin{array}{lll} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right|=0 \ ,

appeared in the proof of the theorem, are equivalent to the known geometric property [1]:

\overrightarrow{P_{\ast}P_1} \cdot S_{_{\triangle P_{\ast}P_2P_3}}+\overrightarrow{P_{\ast}P_2} \cdot S_{_{\triangle P_{\ast}P_3P_1}}+\overrightarrow{P_{\ast}P_3} \cdot S_{_{\triangle P_{\ast}P_1P_2}}=\overrightarrow{\mathbb O} \ .

Geometrical meaning of the determinant

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

is connected with

h=-\frac{1}{S} \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| \quad for \quad S= \left| \begin{array}{cccc} 1 & 1 & 1\\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| ,

which is known as the power of the point P_{\ast} with respect to the circle through the points P_1, P_2, and P_3 (the circumscribed circle of the triangle) [2]. If one denotes the circumcenter of the triangle P_1P_2P_3 by C_{} then

h=|CP_{\ast}|^2-|CP_j|^2 \quad for \ j \in \{1,2,3\} \ ,

and, provided that P_{\ast} lies inside this triangle, the value h_{} is negative.

Spatial case

Results of the previous section can evidently be extended to the case of K=4 points in \mathbb R^{3}. Let the points \{P_j=(x_j,y_j,z_j)\}_{j=1}^4 be noncoplanar, and be counted in such a manner that the value of the determinant

V=\left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ y_1 & y_2 & y_3 & y_4 \\ z_1 & z_2 & z_3 & z_4 \end{array} \right|

is positive.

Т

Теорема [3]. Set

m_1^{\ast}= |P_{\ast}P_1|\cdot \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 & x_4 \\ y_{\ast} & y_2 & y_3 & y_4 \\ z_{\ast} & z_2 & z_3 & z_4 \end{array} \right|,\ m_2^{\ast}= |P_{\ast}P_2|\cdot \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 & x_4 \\ y_1 & y_{\ast} & y_3 & y_4 \\ z_1 & z_{\ast} & z_3 & z_4 \end{array} \right|,\ \dots ;

i.e., m_j^{\ast}=|P_{\ast}P_j| V_j where V_j equals the determinant obtained on replacing the j_{}-th column of V_{} by the column1) \left[1,x_{\ast},y_{\ast},z_{\ast} \right]^{\top}. For these values of weights, the function

F(x,y,z) = \sum_{j=1}^4 m_{j}^{\ast}\sqrt{(x-x_j)^2+(y-y_j)^2+(z-z_j)^2}

has its stationary point at P_{\ast}=(x_{\ast},y_{\ast},z_{\ast}). If P_{\ast} lies inside the tetrahedron P_1P_2P_3P_4, then the values \{m_{j}^{\ast} \} are all positive, and

F(x_{\ast},y_{\ast},z_{\ast})=\min_{(x,y,z)\in \mathbb R^3} F(x,y,z)
=-\ \left| \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ x_{\ast} & x_1 & x_2 & x_3 & x_4 \\ y_{\ast} & y_1 & y_2 & y_3 & y_4 \\ z_{\ast} & z_1 & z_2 & z_3 & z_4 \\ x_{\ast}^2+y_{\ast}^2+z_{\ast}^2 & x_1^2+y_1^2+z_1^2 & x_2^2+y_2^2+z_2^2 & x_3^2+y_3^2+z_3^2 & x_4^2+y_4^2+z_4^2 \end{array} \right| \ .

Proof is similar to that of the planar case.

Geometrical meanings of the values V,\{V_j\}, F(x_{\ast},y_{\ast},z_{\ast}) are similar to their counterparts from the planar case. The value V_{} equals six times the volume of tetrahedron P_1P_2P_3P_4, while the value

-\frac{1}{V}\ \left| \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ x_{\ast} & x_1 & x_2 & x_3 & x_4 \\ y_{\ast} & y_1 & y_2 & y_3 & y_4 \\ z_{\ast} & z_1 & z_2 & z_3 & z_4 \\ x_{\ast}^2+y_{\ast}^2+z_{\ast}^2 & x_1^2+y_1^2+z_1^2 & x_2^2+y_2^2+z_2^2 & x_3^2+y_3^2+z_3^2 & x_4^2+y_4^2+z_4^2 \end{array} \right|

is known as the power of the point P_{\ast} with respect to a sphere circumscribed to that tetrahedron [2]; it is equivalent to

h=|CP_{\ast}|^2-|CP_j|^2 \quad for \ j\in \{1,2,3,4 \} \ ,

where C_{} stands for the circumcenter of the tetrahedron. If P_{\ast} lies inside the tetrahedron, then h_{} is negative.

Multidimensional case

Results of the previous section can evidently be extended to the case of K=n+1 points in \mathbb R^{n}.

Th

Theorem [4]. Let the points \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^{n+1} be noncoplanar and be counted in such a manner that the value

V= \left| \begin{array}{llll} 1 & 1 & \dots & 1\\ x_{11} & x_{21} & \dots & x_{n+1,1} \\ \vdots & \vdots & & \vdots \\ x_{1n} & x_{2n} & \dots & x_{n+1,n} \end{array} \right|

is positive. Denote by V_j the determinant obtained on replacing the j_{}-th column of V_{} by the column2) \left[1,x_{\ast 1},\dots,x_{\ast n} \right]^{\top}. Then for the choice

\left\{m_j^{\ast} = |P_{\ast}P_j| V_j \right\}_{j=1}^{n+1}

the function

F(P) = \sum_{j=1}^{n+1} m_{j}^{\ast} |PP_j|

has its stationary point at P_{\ast}=(x_{\ast 1},\dots,x_{\ast n}). If P_{\ast} lies inside the simplex P_1P_2\dots P_{n+1}, then the values \{ m_j^{\ast} \} are all positive, and

F(P_{\ast})= \displaystyle \sum_{j=1}^{n+1} V_j |P_{\ast}P_j|^2 =- \left| \begin{array}{lllll} 1 & 1 & \dots & 1 & 1 \\ x_{11} & x_{21} & \dots & x_{n+1,1} & x_{\ast 1} \\ \vdots & \vdots & & \vdots & \vdots \\ x_{1n} & x_{2n} & \dots & x_{n+1,n} & x_{\ast n} \\ \displaystyle \sum_{\ell=1}^n x_{1\ell}^2 & \displaystyle \sum_{\ell=1}^n x_{2\ell}^2 & \dots & \displaystyle \sum_{\ell=1}^n x_{n+1,\ell}^2 & \displaystyle \sum_{\ell=1}^n x_{\ast\ell}^2 \end{array} \right| \ .

References

[1].Prasolov V.V. Problems in Plane Geometry. Vol. 2. Nauka. Moscow, 1991, p. 10 (in Russian)

[2]. Uspensky J.V. Theory of Equations. New York. McGraw-Hill. 1948

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

[4]. 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. LNCS. V.8136 , 2013, P. 412-426.

1) , 2) {}^{\top} denotes transposition.

2020/01/03 23:54 редактировал au