Skip to main content
Springer Nature Link
Log in

The Fermat–Torricelli Problem, Part I: A Discrete Gradient-Method Approach

  • Invited Paper
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We give a discrete geometric (differential-free) proof of the theorem underlying the solution of the well known Fermat–Torricelli problem, referring to the unique point having minimal distance sum to a given finite set of non-collinear points in d-dimensional space. Further on, we extend this problem to the case that one of the given points is replaced by an affine flat, and we give also a partial result for the case where all given points are replaced by affine flats (of various dimensions), with illustrative applications of these theorems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Kupitz, Y.S., Martini, H.: Geometric aspects of the generalized Fermat–Torricelli problem. In: Intuitive Geometry. Bolyai Society of Mathematical Studies, vol. 6, pp. 55–127 (1997)

    Google Scholar 

  2. Boltyanski, V., Martini, H., Soltan, V.: Geometric Methods and Optimization Problems. Kluwer, Dordrecht (1999)

    MATH  Google Scholar 

  3. Courant, R., Robbins, H.: What Is Mathematics? Oxford University Press, Oxford (1941)

    Google Scholar 

  4. Martini, H., Swanepoel, K.J., Weiss, G.: The Fermat–Torricelli problem in normed planes and spaces. J. Optim. Theory Appl. 115, 283–314 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Tan, T.V.: An extension of the Fermat–Torricelli problem. J. Optim. Theory Appl. 146, 735–744 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Mordukhovich, B., Nam N, N.: Applications of variational analysis to a generalized Fermat–Torricelli problem. J. Optim. Theory Appl. 148, 431–454 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cockayne, E.J., Melzak, Z.A.: Euclidean constructibility in graph-minimization problems. Math. Mag. 42, 206–208 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3, 177–191 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  9. Mehlhos, S.: Simple counter-examples for the unsolvability of the Fermat- and Steiner–Weber problem by compass and ruler. Beitr. Algebra Geom. 41, 151–158 (2000)

    MathSciNet  MATH  Google Scholar 

  10. Chandrasekaran, R., Tamir, A.: Algebraic optimization: the Fermat–Weber location problem. Math. Program. 46, 219–224 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  11. Martini, H., Weissbach, B.: Napoleon’s theorem with weights in n-space. Geom. Dedic. 74, 213–223 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hajja, M., Martini, H., Spirova, M.: New extensions of Napoleon’s theorem to higher dimensions. Beitr. Algebra Geom. 49, 253–264 (2008)

    MathSciNet  MATH  Google Scholar 

  13. Erdős, P., Vincze, I.: On the approximation of convex, closed plane curves by multifocal ellipses. J. Appl. Probab. 19A, 89–96 (1982). Special Volume: Essays in Statist. Science; Papers in Honour of P.A.P. Moran

    Article  Google Scholar 

  14. Gross, C., Strempel, T.-K.: On generalizations of conics and on a generalization of the Fermat–Torricelli problem. Am. Math. Mon. 105, 732–743 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  15. Nie, J., Parillo, P., Sturmfels, B.: Semidefinite representation of the k-ellipse. In: Algorithms in Algebraic Geometry. IMA Vol. Math. Appl., vol. 146, pp. 117–132. Springer, New York (2008)

    Chapter  Google Scholar 

  16. Kuhn, H.W.: Steiner’s problem revisited. In: Dantzig, G.B., Eaves, B.C. (eds.) Studies in Optimization. MAA Studies in Mathematics, vol. 10, pp. 52–70 (1974). Math. Association of America

    Google Scholar 

  17. Gilbert, E.N., Pollack, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1–29 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  18. Cieslik, D.: Steiner Minimal Trees. Kluwer, Dordrecht (1998)

    Book  MATH  Google Scholar 

  19. Cieslik, D.: Shortest Connectivity. Springer, New York (2005)

    MATH  Google Scholar 

  20. Drezner, Y. (ed.): Facility Location: A Survey of Applications and Methods. Springer, New York (1995)

    Google Scholar 

  21. Eckhoff, J.: Helly, Radon, and Carathéodory type theorems. In: Gruber, P.M., Wills, J.M. (eds.) Handbook of Convex Geometry, pp. 389–448. North-Holland, Amsterdam (1993)

    Google Scholar 

  22. Lindelöf, L.L.: Sur les maxima et minima, d’une fonction des reyons vecteurs menés d’un point mobile à plusieurs centres fixes. Acta Soc. Sci. Finnic. 8, 191–207 (1867)

    Google Scholar 

  23. Kupitz, Y.S., Martini, H.: The Fermat–Torricelli point and isosceles tetrahedra. J. Geom. 49, 150–162 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  24. Heath, Th.: A History of Greek Mathematics, vol. II. Clarendon, Oxford (1921). Reprinted by Dover Publications, 1981

    MATH  Google Scholar 

  25. Durier, R., Michelot, C.: Geometrical properties of the Fermat–Weber problem. Eur. J. Oper. Res. 20, 332–343 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  26. Baronti, M., Casini, E., Papini, P.L.: Centroids, centers, medians: what is the difference? Geom. Dedic. 68, 157–168 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  27. Martini, H., Schöbel, A.: Median and center hyperplanes in Minkowski spaces—a unified approach. Discrete Math. 241, 407–426 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  28. Nievergelt, Y.: Median spheres: theory, algorithms, applications. Numer. Math. 114, 573–606 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  29. Körner, M.-C., Martini, H., Schöbel, A.: Minsum hyperspheres in normed spaces. Discrete Appl. Math. 160, 2221–2233 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel

    Yaakov S. Kupitz

  2. Faculty of Mathematics, University of Technology, 09107, Chemnitz, Germany

    Horst Martini & Margarita Spirova

Authors
  1. Yaakov S. Kupitz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Horst Martini
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Margarita Spirova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Horst Martini.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kupitz, Y.S., Martini, H. & Spirova, M. The Fermat–Torricelli Problem, Part I: A Discrete Gradient-Method Approach. J Optim Theory Appl 158, 305–327 (2013). https://doi.org/10.1007/s10957-013-0266-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-013-0266-z

Keywords

Search

Navigation