The Geodesic 2-center Problem in a Simple Polygon
The geodesic k-center problem in a simple polygon with n vertices consists in the following. Find a set S of k points in the polygon that minimizes the maximum geodesic distance from any point of the polygon to its closest point in S. In this paper, we focus on the case where k=2 and present an exact algorithm that returns a geodesic 2-center in O(n^2^2 n) time.
READ FULL TEXT