!!§!! PCA14, St.Petersburg
----
Analytical approach to the optimal placement
\\
and the point charges problem
\\
\\
\\
\\
Alexei Uteshev
\\
St.Peterburg State University
----
----
~~TOC~~
==Problem==
$$
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 $$
\\
\\
==Problem: L=+1==
$$
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
; ...
{{ algebra2:optimiz:distance:torri:factory.png |}}
\\
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 }
$$
\\
\\
{{ algebra2:optimiz:distance:torri:ftpoint1.png |}}
\\
\\
Steiner tree problem
:
shortest possible network interconnecting
$ \{P_1,\dots,P_K\} \subset \mathbb R^2 $
\\
{{ algebra2:optimiz:distance:torri:steiner_vs_gft1.png |}}
==Problem: L=-1==
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].
==Analytical Solution: L=+1 (GFT) ==
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 \ .
$$
\\
\\
{{ algebra2:optimiz:distance:torri:squares22.png |}}
\\
\\
$$
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
$$
\\
\\
\\
\\
\\
==Analytical Solution: L=+1 (Steiner) ==
Steiner tree problem
: $ n=2,\ K= 4 $
\\
{{ algebra2:optimiz:distance:torri:steiner411.png |}}
\\
\\
$$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
$$
\\
\\
\\
\\
\\
==Difficulties==
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 \\
...
\end{array}
$$
T
:-(:-( hard
!!!
\\
\\
\\
==Bypass==
$$ 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)} \ .
$$
\\
\\
\\
==GFT: 4 points ==
\\
$$ m_1|PP_1|+m_2|PP_1|+m_3|PP_3|+m_4|PP_4| $$
\\
\\
!!Ex!!
$$
\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 \ .
$$
{{ algebra2:optimiz:distance:torri:small_w_11.png |}}
==Coulomb 3 charges: bifurcation picture==
!!Ex.!!
$$
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}}
$$
\\
{{ algebra2:optimiz:distance:torri:3weights1.png |}}
\\
\\
$$
\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 $$
\\
\\
{{ algebra2:optimiz:distance:torri:figure011.png |}}
\\
\\
$$
\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} \ . $$
{{ algebra2:optimiz:distance:torri:stability_param13.png |}}
Conditions for
$ \exists $
4
stationary points
<=>
Conditions for
$ \exists $
1
stable
stationary point
{{ algebra2:optimiz:distance:torri:green03.png |}}
\\
\\
\\
?
Where is the locus of stable equilibrium
?
\\
\\
!!Th.!!
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|
$$
\\
\\
\\
!!Ex.!!
$$ \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)} \ .
$$
{{ algebra2:optimiz:distance:torri:attraction_domain3.png |}}
{{ algebra2:optimiz:distance:torri:attraction_domain2.png |}}
\\
\\
\\
==References==
[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 ☞ ((http://arxiv.org/pdf/1208.3324v1.pdf 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.