The classical Fermat-Torricelli problem consists in finding the point which minimizes the sum of distances from it to the three vertices of a given triangle. This problem has various generalizations. For example, given a subset S of the plane consisting of n points, one can look for a point that minimizes the sum of n distances, i.e., the median of S. A similar question can be asked for a Euclidean space of any dimension or for any metric space. The generalized Fermat-Torricelli problem concerns minimizing a weighted sum of distances, and it is one of the main problems in Facility Location theory. An analytic solution of Fermat-Torricelli problem is non-trivial even in the case of three points, and the general case is quite complex. 

In this work we consider a further generalization, namely the continuous case in which we look for a geometric median of a two-dimensional domain, where the sum of distances is being replaced by an integral. 

It is rather straightforward to see that the median of a convex domain Ω is contained in its interior. In this article we find a universal geometric bound for the distance from the median to the boundary of Ω, which only depends on the area, S(Ω), and its diameter d(Ω). Also, we look into polygonal domains. Even in the case of a triangular domain, one can hardly expect an explicit analytic (closed-form) solution. However, using elementary functions, one can obtain a gradient system for finding the geometric median of a triangular domain. By using a triangulation of a polygonal domain, this result can be generalized to polygonal domains. In addition, we discuss in detail the geometric properties of isosceles triangles.

Petr A. Panov, Senior Lecturer, National Research University Higher School of Economics, 20, Myasnitskaya st., Moscow, 101000, Russian Federation, e-mail: panovpeter@mail.ru

Panov P.A. On the GeometricMedian of Convex, Triangular and Other Polygonal Domains. The Bulletin of Irkutsk State University. Series Mathematics, 2018, vol. 26, pp. 62-75. (in Russian) https://doi.org/10.26516/1997-7670.2018.26.62

1. Panov P.A. Nash Equilibria in the the Facility Location Problem with Externalities. Journal of the New Economic Association, 2017, no. 1(33), pp. 28–42. (in Russian)
2. Savvateev A.V. Zadacha mnogomernogo razmeshheniya i eyo prilozheniya: teoretiko-igrovoj podkhod Doktorskaya dissertatsiya [The Facility Location Problem and Its Applications: the Game Theoretic Approach. Doctoral dissertation]. Moscow, Central Economic Mathematical Institute Publ., 2013, 267 p. (in Russian)
3. Bajaj C. Proving geometric algorithms nonsolvability: An application of factoring polynomials. Journal of Symbolic Computation., 1986, vol. 2, no. 1, pp. 99-102. https://doi.org/10.1016/S0747-7171(86)80015-3
4. Beck A., Sabach S. Weiszfeld’s method: old and new results. J. Optim. Theory Appl, 2013, vol. 164, no. 1, pp. 1-40. https://doi.org/10.1007/s10957-014-0586-7
5. Boltyanski V., Martini H., Soltan V. Geometric Methods and Optimization Problems, Vol. 4 of Combinatorial Optimization. Springer Science & Business Media, 1999, 429 p.
6. Carlsson J., Jia F., Li Y. An approximation algorithm for the continuous k-medians problem in a convex polygon. INFORMS Journal on Computing, 2013, vol. 26, no. 2, pp. 280-289. https://doi.org/10.1287/ijoc.2013.0564
7. Carmi P., Har-Peled S., Katz M. On the Fermat–Weber center of a convex object. Computational Geometry, 2005, vol. 32, no. 3, pp. 188-195. https://doi.org/10.1016/j.comgeo.2005.01.002
8. Drezner Z., Hamacher H.W. (eds.) Facility Location. Applications and Theory. Berlin, Springer-Verlag, 2002, 464 p.
9. Encyclopedia of Mathematics, Fermat-Torricelli problem, Weber problem, Fermat point. Available at: https://www.encyclopediaofmath.org (date of access: September 2018).
10. Fekete S., Mitchell J., Beurer K. On the continuous Fermat-Weber problem. Operations Research, 2005, vol. 53, no. 1, pp. 61-76. https://doi.org/10.1287/opre.1040.0137
11. Mallows C., Another comment on O’Cinneide. The American Statistician, 1991, vol. 45, no 3, p. 257. https://doi.org/10.1080/00031305.1991.10475815
12. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer. Math. Monthly, 2014, vol. 121, no. 4, pp. 318-331 https://doi.org/10.4169/amer.math.monthly.121.04.318.
13. Wesolowsky G. The Weber problem: History and perspectives. Location Science, 1993, vol. 1, no. 1, pp. 5-23.
14. Zhang T., Carlsson J. On the Continuous Fermat-Weber Problem for a Convex Polygon Using Euclidean Distance. Available at: https://arxiv.org/abs/1403.3715, 2014 (date of access: September 2018).