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 (внешнее изменение)