The Geodesic 2-center Problem in a Simple Polygon

10/25/2017
by   Eunjin Oh, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset