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.
Similar content being viewed by others
References
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)
Boltyanski, V., Martini, H., Soltan, V.: Geometric Methods and Optimization Problems. Kluwer, Dordrecht (1999)
Courant, R., Robbins, H.: What Is Mathematics? Oxford University Press, Oxford (1941)
Martini, H., Swanepoel, K.J., Weiss, G.: The Fermat–Torricelli problem in normed planes and spaces. J. Optim. Theory Appl. 115, 283–314 (2002)
Tan, T.V.: An extension of the Fermat–Torricelli problem. J. Optim. Theory Appl. 146, 735–744 (2010)
Mordukhovich, B., Nam N, N.: Applications of variational analysis to a generalized Fermat–Torricelli problem. J. Optim. Theory Appl. 148, 431–454 (2011)
Cockayne, E.J., Melzak, Z.A.: Euclidean constructibility in graph-minimization problems. Math. Mag. 42, 206–208 (1969)
Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3, 177–191 (1988)
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)
Chandrasekaran, R., Tamir, A.: Algebraic optimization: the Fermat–Weber location problem. Math. Program. 46, 219–224 (1990)
Martini, H., Weissbach, B.: Napoleon’s theorem with weights in n-space. Geom. Dedic. 74, 213–223 (1999)
Hajja, M., Martini, H., Spirova, M.: New extensions of Napoleon’s theorem to higher dimensions. Beitr. Algebra Geom. 49, 253–264 (2008)
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
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)
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)
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
Gilbert, E.N., Pollack, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1–29 (1968)
Cieslik, D.: Steiner Minimal Trees. Kluwer, Dordrecht (1998)
Cieslik, D.: Shortest Connectivity. Springer, New York (2005)
Drezner, Y. (ed.): Facility Location: A Survey of Applications and Methods. Springer, New York (1995)
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)
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)
Kupitz, Y.S., Martini, H.: The Fermat–Torricelli point and isosceles tetrahedra. J. Geom. 49, 150–162 (1994)
Heath, Th.: A History of Greek Mathematics, vol. II. Clarendon, Oxford (1921). Reprinted by Dover Publications, 1981
Durier, R., Michelot, C.: Geometrical properties of the Fermat–Weber problem. Eur. J. Oper. Res. 20, 332–343 (1985)
Baronti, M., Casini, E., Papini, P.L.: Centroids, centers, medians: what is the difference? Geom. Dedic. 68, 157–168 (1997)
Martini, H., Schöbel, A.: Median and center hyperplanes in Minkowski spaces—a unified approach. Discrete Math. 241, 407–426 (2001)
Nievergelt, Y.: Median spheres: theory, algorithms, applications. Numer. Math. 114, 573–606 (2010)
Körner, M.-C., Martini, H., Schöbel, A.: Minsum hyperspheres in normed spaces. Discrete Appl. Math. 160, 2221–2233 (2012)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-013-0266-z