On the geometric median of convex, triangular and other polygonal domains

P. A. Panov

The Bulletin of Irkutsk State University. Series Mathematics, Tome 26 (2018), pp. 62-75

Résumé

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 $\Omega$ is contained in its interior. In this article we find a universal geometric bound for the distance from the median to the boundary of $\Omega$, which only depends on the area, $S(\Omega)$, and its diameter $d(\Omega)$. 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.

Détail

Keywords: geometric median, location problem, distance to the boundary, gradient system.
Mots-clés : convex domain

Bibliographie

[1] Panov P. A., “Nash Equilibria in the the Facility Location Problem with Externalities”, Journal of the New Economic Association, 2017, no. 1(33), 28–42 (in Russian) | MR

[2] Savvateev A. V., The Facility Location Problem and Its Applications: the Game Theoretic Approach, Doctoral dissertation, Central Economic Mathematical Institute Publ., M., 2013, 267 pp. (in Russian)

[3] Bajaj C., “Proving geometric algorithms nonsolvability: An application of factoring polynomials”, Journal of Symbolic Computation, 2:1 (1986), 99–102 | DOI | MR

[4] Beck A., Sabach S., “Weiszfeld's method: old and new results”, J. Optim. Theory Appl., 164:1 (2013), 1–40 | DOI | MR

[5] Boltyanski V., Martini H., Soltan V., Geometric Methods and Optimization Problems, v. 4, Combinatorial Optimization, Springer Science Business Media, 1999, 429 pp. | MR

[6] Carlsson J., Jia F., Li Y., “An approximation algorithm for the continuous $k$-medians problem in a convex polygon”, INFORMS Journal on Computing, 26:2 (2013), 280–289 | DOI | MR

[7] Carmi P., Har-Peled S., Katz M., “On the Fermat-Weber center of a convex object”, Computational Geometry, 32:3 (2005), 188–195 | DOI | MR | Zbl

[8] Drezner Z., Hamacher H. W. (eds.), Facility Location. Applications and Theory, Springer-Verlag, Berlin, 2002, 464 pp. | MR | Zbl

[9] Fermat-Torricelli problem, Weber problem, Fermat point, Encyclopedia of Mathematics, (date of access: September, 2018) https://www.encyclopediaofmath.org

[10] Fekete S., Mitchell J., Beurer K., “On the continuous Fermat-Weber problem”, Operations Research, 53:1 (2005), 61–76 | DOI | MR | Zbl

[11] Mallows C., “Another comment on O'Cinneide”, The American Statistician, 45:3 (1991), 257 | DOI

[12] Uteshev A. Yu., “Analytical Solution for the Generalized Fermat-Torricelli Problem”, Amer. Math. Monthly, 121:4 (2014), 318–331 | DOI | MR | Zbl

[13] Wesolowsky G., “The Weber problem: History and perspectives”, Location Science, 1:1 (1993), 5–23 | Zbl

[14] Zhang T., Carlsson J., On the Continuous Fermat-Weber Problem for a Convex Polygon Using Euclidean Distance, 2014, arXiv: (date of access: September, 2018) 1403.3715 [cs.CG]