|
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.
Received: 24.08.2018
Citation:
P. A. Panov, “On the geometric median of convex, triangular and other polygonal domains”, Bulletin of Irkutsk State University. Series Mathematics, 26 (2018), 62–75
Linking options:
https://www.mathnet.ru/eng/iigum357 https://www.mathnet.ru/eng/iigum/v26/p62
|
Statistics & downloads: |
Abstract page: | 234 | Full-text PDF : | 124 | References: | 30 |
|