# VMath

### Основное

#### Действия

§

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

Т

Теорема [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 \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 [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.
matricese/optimize/distancee/torri_e/inverse.txt · Последние изменения: 2020/03/11 14:00 (внешнее изменение)