Computing the Geodesic Centers of a Polygonal Domain∗
Sang Won, Bae Matias Korman, Yoshio Okamoto · 2015
We present an algorithm that exactly computes the geodesic center of a given polygonal domain. The run-ning time of our algorithm is O(n12+) for any > 0, where n is the number of corners of the input polygonal domain. Prior to our work, only the very special case where a simple polygon is given as input has been in-tensively studied in the 1980s, and an O(n log n)-time algorithm is known by Pollack et al. Our algorithm is the first one that handles general polygonal domains that may have one or more polygonal holes. 1