RUS  ENG
Full version
JOURNALS // Bulletin of Irkutsk State University. Series Mathematics // Archive

Bulletin of Irkutsk State University. Series Mathematics, 2018 Volume 26, Pages 62–75 (Mi iigum357)

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

P. A. Panov

National Research University Higher School of Economics, Moscow, Russian Federation

Abstract: 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.

Keywords: geometric median, location problem, convex domain, distance to the boundary, gradient system.

UDC: 519.863

MSC: 52B55

Received: 24.08.2018

DOI: 10.26516/1997-7670.2018.26.62



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024