The geodesic k-center problem in a simple polygon with n vertices consists in the following. Find k points, called centers, in the polygon to minimize the maximum geodesic distance from any point of the polygon to its closest center. In this paper, we focus on the case where k = 2 and present an exact algorithm that returns an optimal geodesic 2-center in O(n~2 log~2 n) time.
展开▼
