View source for Fermat-Torricelli problem

''Torricelli–Fermat problem''

The (generalized) Fermat–Torricelli problem, incorrectly also called the Steiner–Weber problem, refers to finding the unique point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300501.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300502.png" />, minimizing the function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300503.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

for a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300504.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300505.png" /> given non-collinear points with corresponding positive weights <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300506.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300507.png" /> denotes the Euclidean norm.

In 1638, R. Descartes invited P. de Fermat to investigate (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300508.png" />) curves of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f1300509.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

which led Fermat to ask in 1643 for the minimum point with respect to the unweighted subcase <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005010.png" /> of (a1) (i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005011.png" />), cf. [[#References|[a14]]], p. 153. The first solution to this subcase was obtained by E. Torricelli (see [[#References|[a29]]], [[#References|[a30]]]) using the focal property of the [[Ellipse|ellipse]], and further ruler-and-compass constructions were given by B. Cavalieri, V. Viviani, Th. Simpson, and H. Lebesgue; the unweighted case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005012.png" /> was solved by G. Fagnano, cf. [[#References|[a34]]], [[#References|[a20]]], and [[#References|[a2]]], Chap. II, for extensive historical discussions and corrections. With the help of [[Galois theory|Galois theory]] it was proved in [[#References|[a6]]] and [[#References|[a1]]] that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005013.png" /> points in [[General position|general position]] the Fermat–Torricelli problem does not allow exact algorithms under computation models with arithmetic operations and extraction of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005014.png" />th roots. On the other hand, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005015.png" />-approximative solutions for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005016.png" /> can be constructed in polynomial time, see [[#References|[a4]]]. The weighted case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005017.png" /> was completely solved by W. Launhardt [[#References|[a21]]]; its relations to generalizations of the Napoleon theorem (also for higher dimensions) were investigated in [[#References|[a24]]]. In 1846, E. Fasbender [[#References|[a13]]] proved that the unweighted case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005018.png" /> of minimizing (a1) is dual to the construction of the largest equilateral triangle circumscribed to the triangle <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005019.png" />, and H.W. Kuhn [[#References|[a19]]] pointed out that this Vecten–Fasbender duality is historically the first example of dualizing a problem in the spirit of [[Non-linear programming|non-linear programming]].

For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005020.png" />, the level curves (a2) of the function (a1) (with equal weights) are called poly-ellipses or multifocal ellipses. They were first studied by E.W. von Tschirnhaus [[#References|[a31]]], who extended the classical gardener's string construction from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005021.png" /> in (a2) to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005022.png" />. Many further properties and applications of these curves (and of their analogues in the weighted and higher-dimensional situation) are collected in [[#References|[a25]]], [[#References|[a12]]] and [[#References|[a16]]].

Analytic approaches to the minimum point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005023.png" /> of (a1) were presented by J. Bertrand, R. Sturm, L.L. Lindelöf, Kuhn, C. Witzgall, and many others; in modern terms they can be summarized by the following theorem (see, e.g., [[#References|[a18]]]):

I) The minimum point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005024.png" /> of (a1) exists and is unique.

II) If for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005025.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005026.png" /></td> </tr></table>

holds, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005027.png" /> and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005028.png" /></td> </tr></table>

III) If there is a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005029.png" /> satisfying

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005030.png" /></td> </tr></table>

then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005031.png" />.

These characterizations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005032.png" /> have a realistic appeal, since (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005033.png" />) there is even a mechanical device based on the so-called Varignon frame: A board is drilled with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005034.png" /> holes at the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005035.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005036.png" /> strings are tied together in a knot at one end, the loose ends are passed through the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005037.png" /> holes and are attached to physical weights below the board. The equilibrium position of the knot yields the solution. This was presented by G. Pick in [[#References|[a32]]], Math. Appendix, but the early history of this approach is discussed in [[#References|[a15]]].

The first algorithmic approach to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005038.png" /> was provided by E. Weiszfeld [[#References|[a33]]], see also [[#References|[a18]]]. It is gradient descent but not convergent at the foci <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005039.png" /> (cf. also [[Gradient method|Gradient method]]). L.M. Ostresh [[#References|[a27]]] proposed the first completely convergent iteration procedure, which can even be applied in Banach spaces, see [[#References|[a11]]].

The Fermat–Torricelli problem has been one of the starting points of location science from [[Operations research|operations research]], in particular belonging to the field of continuous location theory, where it is usually called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005041.png" />-median problem or single facility location problem, cf. [[#References|[a8]]], [[#References|[a22]]], and from the historical point of view also [[#References|[a21]]], [[#References|[a32]]] (see also [[Weber problem|Weber problem]]).

Since local conditions for Steiner points in Steiner minimal trees (cf. also [[Steiner tree problem|Steiner tree problem]]; [[Steiner point|Steiner point]]) are based on properties of Fermat–Torricelli points, a related passage in [[#References|[a7]]], pp. 354–361, can be considered as starting point of investigations in this direction (although the respective question goes back even to C.F. Gauss, 1836: To connect four towns by a network of minimal total length). For historical corrections with respect to Steiner minimal trees (including the fact that even the name is not justified, analogous to the wrong phrase  "Steiner–Weber problem"  instead of  "Fermat–Torricelli problem" ) see [[#References|[a20]]] and [[#References|[a2]]], Sect. 23.9; a modern treatment of Steiner minimal trees is [[#References|[a5]]].

==Generalizations.==
Generalizations of the problem to minimize (a1) were mainly studied in two directions.

Extensions to finite-dimensional normed spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005042.png" /> (i.e., Minkowski spaces) or other non-Euclidean spaces: For example, denoting by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005043.png" /> the (in Minkowski spaces not necessarily point-shaped) solution set, the property <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005044.png" /> holds for all finite point sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005045.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005046.png" />, if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005047.png" /> is an [[Inner product|inner product]] space [[#References|[a9]]]. Various further properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005048.png" /> were investigated in [[#References|[a10]]], see also [[#References|[a3]]]. Extensions to other non-Euclidean spaces are considered in [[#References|[a11]]], [[#References|[a26]]].

Modification of the given geometric configuration: For example, replacing the searched point in (a1) by a hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005049.png" />, one gets the median hyperplane problem (also called linear fit problem, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005051.png" /> regression problem), which can be formulated with respect to vertical and orthogonal distances. The importance of this problem (e.g., compared with the known least-squares regression) for [[Robust statistics|robust statistics]] is based on the fact that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005052.png" /> estimates are technically robust against arbitrary outliers, cf. [[#References|[a28]]]. Also, such problems are studied in linear [[Approximation theory|approximation theory]] and [[Computational geometry|computational geometry]] (also in relation to the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005054.png" />-set problem). Position criteria for median hyperplanes of weighted point sets and algorithmical approaches are presented in [[#References|[a17]]] (for Euclidean <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005055.png" />-spaces) and in [[#References|[a23]]] (for other Minkowski <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005056.png" />-spaces).

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Bajaj,   "The algebraic degree of geometric optimization problems."  ''Discr. Comput. Geom.'' , '''3'''  (1988)  pp. 177–191</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  V. Boltyanski,   H. Martini,   V. Soltan,   "Geometric methods and optimization problems" , Kluwer Acad. Publ.  (1999)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.D. Chakerian,   M.A. Ghandehari,   "The Fermat problem in Minkowski spaces."  ''Geom. Dedicata'' , '''17'''  (1985)  pp. 227–238</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Chandrasekaran,   A. Tamir,   "Algebraic optimization: The Fermat–Weber problem"  ''Math. Programming'' , '''46'''  (1990)  pp. 219–224</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D. Cieslik,   "Steiner minimal trees" , Kluwer Acad. Publ.  (1999)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E.J. Cockayne,   Z.A. Melzak,   "Euclidean constructibility in graph-minimization problems"  ''Math. Mag.'' , '''42'''  (1969)  pp. 206–208</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R. Courant,   H. Robbins,   "What is mathematics?" , Oxford Univ. Press  (1941)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  "Facility location: A survey on applications and methods"  Z. Drezner (ed.) , ''Ser. in Operations Research'' , Springer  (1995)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R. Durier,   "The Fermat–Weber problem and inner product spaces"  ''J. Approx. Th.'' , '''78'''  (1994)  pp. 161–173</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  R. Durier,   C. Michelot,   "Geometrical properties of the Fermat–Weber problem"  ''European J. Oper. Res.'' , '''20'''  (1985)  pp. 332–343</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  U. Eckhardt,   "Weber's problem and Weiszfeld's algorithm in general spaces"  ''Math. Programming'' , '''18'''  (1980)  pp. 186–196</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  P. Erdös,   I. Vincze,   "On the approximation of convex, closed plane curves by multifocal ellipses"  ''J. Appl. Probab.'' , '''19A'''  (1982)  pp. 89–96</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  E. Fasbender,   "Über die gleichseitigen Dreiecke, welche um ein gegebenes Dreieck gelegt werden können"  ''J. Reine Angew. Math.'' , '''30'''  (1846)  pp. 230–231</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  P. de Fermat,   "Œvres" , '''I''' , H. Tannery (ed.), Paris  (1891)  (Supplement: Paris 1922)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  O.I. Franksen,   I. Gratan–Guinness,   "The earliest contribution to location theory? Spatio-economic equilibrium with Lamé and Clapeyron (1829)"  ''Math. and Computers in Simulation'' , '''31'''  (1989)  pp. 195–220</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  C. Gross,   T.-K. Strempel,   "On generalizations of conics and on a generalization of the Fermat–Torricelli point"  ''Amer. Math. Monthly'' , '''105'''  (1998)  pp. 732–743</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  N.M. Korneenko,   H. Martini,   "Hyperplane approximation and related topics"  J. Pach (ed.) , ''New Trends in Discrete and Computational Geometry'' , Springer  (1993)  pp. 135–162</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  H.W. Kuhn,   "Steiner's problem revisited"  G.B. Dantzig (ed.)  B.C. Eaves (ed.) , ''Studies in Optimization'' , ''Studies in Math.'' , '''10''' , Math. Assoc. Amer.  (1974)  pp. 52–70</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  H.W. Kuhn,   "Nonlinear programming: A historical view"  R.W. Cottle (ed.)  C.W. Lemke (ed.) , ''SIAM–AMS Proc.'' , '''9''' , Amer. Math. Soc.  (1976)  pp. 1–26</TD></TR><TR><TD valign="top">[a20]</TD> <TD valign="top">  Y.S. Kupitz,   H. Martini,   "Geometric aspects of the generalized Fermat–Torricelli problem"  I. Básrásny (ed.)  K. Böröczky (ed.) , ''Intuitive Geometry (Budapest, 1995)'' , '''6''' , Bolyai Soc. Math. Studies  (1997)  pp. 55–127</TD></TR><TR><TD valign="top">[a21]</TD> <TD valign="top">  W. Launhardt,   "Kommercielle Tracirung der Verkehrswege" , Hannover  (1872)</TD></TR><TR><TD valign="top">[a22]</TD> <TD valign="top">  R.F. Love,   J.G. Morris,   G.O. Wesolowsky,   "Facilities location: models and methods" , North-Holland  (1988)</TD></TR><TR><TD valign="top">[a23]</TD> <TD valign="top">  H. Martini,   A. Schöbel,   "Median hyperplanes in normed spaces — a survey"  ''Discr. Appl. Math.'' , '''89'''  (1998)  pp. 181–195</TD></TR><TR><TD valign="top">[a24]</TD> <TD valign="top">  H. Martini,   B. Weissbach,   "Napoleon's theorem with weights in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005057.png" />-space"  ''Geom. Dedicata'' , '''74'''  (1999)  pp. 213–223</TD></TR><TR><TD valign="top">[a25]</TD> <TD valign="top">  Z.A. Melzak,   J.S. Forsyth,   "Polyconics 1: Polyellipses and optimization"  ''Quart. Appl. Math.'' , '''35'''  (1977)  pp. 239–255</TD></TR><TR><TD valign="top">[a26]</TD> <TD valign="top">  R. Noda,   T. Sakai,   M. Morimoto,   "Generalized Fermat's problem."  ''Canad. Math. Bull.'' , '''34'''  (1991)  pp. 96–104</TD></TR><TR><TD valign="top">[a27]</TD> <TD valign="top">  L.M. Ostresh,   "On the convergence of a class of iterative methods for solving the Weber location problem"  ''Operat. Res.'' , '''26'''  (1978)  pp. 597–609</TD></TR><TR><TD valign="top">[a28]</TD> <TD valign="top">  P.J. Rousseeuw,   A.M. Leroy,   "Robust regression and outlier detection" , Wiley  (1987)</TD></TR><TR><TD valign="top">[a29]</TD> <TD valign="top">  E. Torricelli,   "Opere" , '''I/2''' , Faënza  (1919)  pp. 90–97</TD></TR><TR><TD valign="top">[a30]</TD> <TD valign="top">  E. Torricelli,   "Opere" , '''III''' , Faënza  (1919)  pp. 426–431</TD></TR><TR><TD valign="top">[a31]</TD> <TD valign="top">  E.W. von Tschirnhaus,   "Medicina mentis" , Lipsiae  (1695)  (German ed. by R. Zaunick, Acta Historica Leopoldina, J.A. Barth, Leipzig 1963)</TD></TR><TR><TD valign="top">[a32]</TD> <TD valign="top">  A. Weber,   "Über den Standort der Industrien, Teil I: Reine Theorie des Standorts" , J.C.B. Mohr, Tübingen  (1909)  (English ed. by C.J. Friedrichs, Univ. Chicago Press, 1929)</TD></TR><TR><TD valign="top">[a33]</TD> <TD valign="top">  E. Weiszfeld,   "Sur le point pour lequel la somme des distances de <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f130/f130050/f13005058.png" /> points donnés est minimu"  ''Tôhoku Math. J.'' , '''43'''  (1937)  pp. 355–386</TD></TR><TR><TD valign="top">[a34]</TD> <TD valign="top">  G.O. Wesolowsky,   "The Weber problem — history and perspectives"  ''J. Location Sci.'' , '''1'''  (1993)  pp. 5–23</TD></TR></table>