Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons

Given a set of m point sites in a simple polygon, the geodesic nearest-point Voronoi diagram of the sites partitions the polygon into m Voronoi cells, one cell per site, such that every point in a cell has the same nearest site under the geodesic metric. In this paper, we present an O(n + m log m)-time algorithm for computing the geodesic nearest-point Voronoi diagram of m points in a simple n-gon. This matches the best known lower bound of Ω(n + m log m) as well as improving the previously best known algorithms which take time O(n + m log m + m log2 n) and O(n log n + m log m). This answers the longstanding question whether the geodesic nearest-point Voronoi diagram can be computed optimally, which was explicitly posed by Aronov [Algorithmica, 1989] and Mitchell [Handbook of Computational Geometry, 2000].