On the geodesic centers of polygonal domains

Haitao Wang


In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain $P$ with a total of $n$ vertices. We discover many interesting observations. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of $P$ that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the combinatorial size of the shortest path map equivalence decomposition of $P$, which is known to be $O(n^{10})$. One key observation is a $\pi$-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in $O(n^{11} \log n)$ time. Previously, an algorithm of $O(n^{12+\epsilon})$ time was known for this problem, for any $\epsilon > 0$.

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v9i1a5

ISSN: 1920-180X