$$ F(P) = m_1|PP_1|^L+\dots+ m_K|PP_K|^L \to \min_{P\in \mathbb R^n} $$

$$ \{P_1,\dots,P_K\} \subset \mathbb R^n,\ \{m_1,\dots,m_K\} \subset \mathbb R $$

$$ | \cdot | - \mbox{ Euclidean metrics } $$

$$ 0\ne L \in \mathbb R $$

$$ m_1 |PP_1|+\dots+ m_K |PP_K| \to \min_{P\in \mathbb R^n } $$

$$ n=2_{} $$

Facility location problem : Launhardt , 1872 ; Alfred Weber , 1909 ; …

Generalized Fermat-Torricelli problem

Fermat , 1638

Datis tribus punctis, quartum reperire, a quo si ducantur tres rectæ ad data puncta, summa trium harum rectarum sit minima quantitas

$$ |PP_1|+|PP_2| +|PP_3| \to \min_{P\in \triangle P_1P_2P_3 } $$

Steiner tree problem : shortest possible network interconnecting $ \{P_1,\dots,P_K\} \subset \mathbb R^2 $

Point charges: equilibrium positions for $$ F(P)=\frac{m_1}{|PP_1|}+\dots+ \frac{m_K}{|PP_K|} $$ Coulomb's or Newton's potentials

Maxwell's conjecture: The number of stationary points $ \le (K-1)^2 $. [Not proved].

Generalized Fermat-Torricelli problem : $ n=2,\ K= 3 $

$$ F(P)=m_1|PP_1|+m_2|PP_2|+m_3|PP_3| \to \min_{P\in \mathbb R^2} $$

$$ P_{\ast}=\frac{K_1 K_2 K_3}{4 |S| \sigma d} \left( \frac{P_1}{K_1}+\frac{P_2}{K_2}+\frac{P_3}{K_3} \right) \ , $$ $$ d=\frac{1}{2\, \sigma}(m_1^2K_1+m_2^2K_2+m_3^2K_3) = \left[ \min_{P\in \triangle P_1P_2P_3} F(P) \right]^2 \ . $$

$$ K_1=\left(|P_1P_2|^2+|P_1P_3|^2-|P_2P_3|^2 \right) \sigma+(m_2^2+m_3^2-m_1^2)S $$ $$ K_2= \dots , K_3=\dots $$

Steiner tree problem : $ n=2,\ K= 4 $

$$d=\frac{1}{2} \sqrt{\begin{array}{ll} \left[x_1+x_2-x_3-x_4+\sqrt{3}(-y_1+y_2+y_3-y_4)\right]^2 \\ +\left[\sqrt{3}(x_1-x_2-x_3+x_4)+ y_1+y_2-y_3-y_4\right]^2 \end{array} } $$

$$ t_{1 x}= \frac{\mathbf{poly}_1 (\{x_j,y_j\}_{j=1}^4) }{d^2},\ t_{1y} =\frac{\mathbf{poly}_2 (\{x_j,y_j\}_{j=1}^4) }{d^2}, \ t_{2 x}= \dots, \ t_{2 y}= \dots $$

Generalized Fermat-Torricelli problem : $ n=2,\ K= 4 $

$$ F(P)=m_1|PP_1|+m_2|PP_2|+m_3|PP_3|+m_4|PP_4| \to \min_{P\in \mathbb R^2} $$

Coulomb's potential : $ n=2,\ K= 3 $; stationary points

$$ F(P)=\frac{m_1}{|PP_1|}+\frac{m_2}{|PP_2|}+\frac{m_3}{|PP_3|} $$

Gradient systems $$ \frac{D\, F}{D\, P} = \mathbb O $$

Reduction to an algebraic system $$ \begin{array}{c} \left\{\begin{array}{l} \displaystyle \frac{m_1(x-x_1)}{\sqrt{(x-x_1)^2+(y-y_1)^2}^3}+ \frac{m_2(x-x_2)}{\sqrt{(x-x_2)^2+(y-y_2)^2}^3}+ \frac{m_3(x-x_3)}{\sqrt{(x-x_3)^2+(y-y_3)^2}^3} = 0, \\ \\ \\ \displaystyle \frac{m_1(y-y_1)}{\sqrt{(x-x_1)^2+(y-y_1)^2}^3}+ \frac{m_2(y-y_2)}{\sqrt{(x-x_2)^2+(y-y_2)^2}^3}+ \frac{m_3(y-y_3)}{\sqrt{(x-x_3)^2+(y-y_3)^2}^3} = 0 \end{array} \right. \\ \Downarrow \\ {\rm Squaring \ procedure} \\ \Downarrow \\ \left\{ \begin{array}{ll} F_1(x,y,m_1,m_2, m_3) = 0, \\ F_2(x,y,m_1, m_2,m_3) = 0, \end{array} \right. \deg_{[x,y]} F_j = 28 \\ \Downarrow \\ {\rm Elimination \ of \ variable} \\ \Downarrow \\ \ldots \end{array} $$ T hard !!!

$$ F(P)=m_1|PP_1|^L+m_2|PP_2|^L+m_3|PP_3|^L $$

$$ \left\{ \begin{array}{ccc} m_1|PP_1|^{L-2} (x-x_1)+m_2|PP_2|^{L-2} (x-x_2)+m_3|PP_3|^{L-2} (x-x_3)&=&0, \\ m_1|PP_1|^{L-2} (y-y_1)+m_2|PP_2|^{L-2} (y-y_2)+m_3|PP_3|^{L-2} (y-y_3)&=&0. \\ \end{array} \right. $$

Linear system w.r.t. $ m_1,m_2,m_3 $

$$ 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) $$

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

$$ \left[\frac{m_2S_1}{m_1S_2} \right]^2= \left[\frac{|PP_2|}{|PP_1|}\right]^{2(2-L)},\ \left[\frac{m_2S_3}{m_3S_2} \right]^2= \left[\frac{|PP_2|}{|PP_3|} \right]^{2(2-L)} \ . $$

$$ m_1|PP_1|+m_2|PP_1|+m_3|PP_3|+m_4|PP_4| $$

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

$$ \begin{array}{c} \left\{ \begin{array}{l} F_1(x,y,m) = 0, \\ F_2(x,y,m) = 0, \end{array} \right. \deg_{[x,y]} F_j = 12 \\ \\ \\ \Downarrow \\ \\ \\ {\rm Elimination \ of \ variables} \\ \\ \\ \Downarrow \\ \\ \\ \mathbf{Resultant}_y(F_1,F_2) =\mathcal X(x,m) \\ \\ \\ \Downarrow \\ \\ \\ \deg_x (\ ) = 12 \end{array} $$

Find the locus of stationary point for any $ m $:

$$ \begin{array}{c} \mathbf{Resultant}_m(F_1,F_2) = \Phi(x,y) \\ \\ \Downarrow \\ \\ \deg \Phi(x,y) = 96 \\ \\ \Downarrow \\ \\ \\ \end{array} $$ $$ \Phi_0(x,y) =3\,y(-7\,y+10\,x)(8\,x-y)(2\,x-9\,y)(x^2+y^2)^4+ $$ $$ +\dots -1152\, (2823793\,x^2-22813720\,xy-56866\,y^2)+4409856 (1491\,x+1234\,y)-2110116096 \ . $$

$$ 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}} $$

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

Find the locus of stationary point for any $ m_2, m_3 $:

$$ \widetilde F_1(x,y,m_2) = 0 $$

$$ \mathbf{Resultant}_x (\widetilde F_1, \widetilde F_2)\equiv (y-1)^8(y-6)^4 \mathcal Y(y,m_2,m_3), \ \deg_y \mathcal Y =34 \ . $$

2 vs. 4 stationary point

$$ \mathbf{Discriminant}_y( \mathcal Y(y,m_2,m_3)) \equiv \Xi^2(m_2,m_3) \Psi(m_2,m_3) \quad , \quad \deg \Xi=444, \deg \Psi =48 $$

$$ \Psi(m_2,m_3)= $$ $$ =3^{36}(169\,m_2^2+192\,m_2m_3+64\,m_3^2)^5(169\,m_2^2 -192\,m_2m_3+64\,m_3^2)^5(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} \ . $$

Conditions for $ \exists $ 4 stationary points

<=> Conditions for $ \exists $ 1 stable stationary point

? Where is the locus of stable equilibrium ?

If $ (m_1,m_2,m_2) \in $ stability domain in parameter space => stable stationary point $ \in $ $$ \Phi(x,y) > \frac{2}{9} S^2 \ . $$

$$ \Phi(x,y)= \frac{S_1(x,y)S_2(x,y)S_3(x,y)}{|PP_1|^2 |PP_2|^2 |PP_3|^2} \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x& x_1 & x_2 & x_3 \\ y& y_1 & y_2 & y_3 \\ x^2+y^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \end{array} \right| \ . $$ with $$ 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| $$ $$ S=S_1+S_2+S_3= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| $$

$$ \begin{array}{c} P_1 =(1,1) \\ m_1 \end{array} , \begin{array}{c} P_2=(5,1) \\ m_2 \end{array} , \begin{array}{c} P_3= (2,6) \\ m_3 \end{array} $$

$$ \Phi(x,y)=\frac{16(28-5\,x-3\,y)(5\,x-y-4)(y-1)(-52+30\,x+32\,y-5\,x^2-5\,y^2)}{((x-1)^2+(y-1)^2)((x-5)^2+(y-1)^2)((x-2)^2+(y-6)^2)} \ . $$

[1]. Launhardt W. Kommercielle Tracirung der Verkehrswege. Zeitschrift f. Architekten u.Ingenieur-Vereinis im Königreich Hannover. 18, 516-534, 1872.

[2]. Maxwell J.C. A Treatise on Electricity and Magnetism. Vol. 1. Dower, New York. 1954

[3]. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer.Math.Monthly. 121, N 4, 318-331, 2014. Preprint ☞ arXive:1208.3324v1 (220 Kb)

[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. 8136, 412-426, 2013.

[5]. Weber A. Über den Standort der Industrie. Bd. 1: Reine Theorie des Standorts. Tübingen. J.C.B.Mohr, 1909.