**((users:au:index_e Author))** --- **((:algebra2:optimiz:distance:torri:inverse Русская версия))**
----
!!§!! Satellite page for
☞
((:matricese:optimize:distancee:torri_e Fermat-Torricelli problem and its development))
----
==Inverse problem for the Fermat-Torricelli problem==
~~TOC~~
**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** ((#references [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 $.
{{ algebra2:optimiz:distance:torri:inverse1.jpg |}}
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
((#references [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)
((#references [2])). If one denotes the circumcenter of the triangle $ P_1P_2P_3 $ by $ C_{} $ then
$$
h=|CP_{\ast}|^2-|CP_j|^2 \quad \mbox{ 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.
!!Т!! **Теорема** ((#references [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 column//[[$ {}^{\top} $ denotes transposition.]] $ \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 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** ((#references [2])); it is equivalent to
$$ h=|CP_{\ast}|^2-|CP_j|^2 \quad \mbox{ 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** ((#references [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 column//[[$ {}^{\top} $ denotes transposition.]] $ \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
☞
((http://www.apmath.spbu.ru/ru/staff/uteshev/publ/publ1.pdf 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.