Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes

We investigate the higher-order Voronoi diagrams of n point sites with respect to the geodesic distance in a simple polygon with h > 0 polygonal holes and c corners. Given a set of n point sites, the kth order Voronoi diagram partitions the plane into several regions such that all points in a region share the same k nearest sites. The nearest-site (first-order) geodesic Voronoi diagram has already been well-studied, and its total complexity is O (n + c). On the other hand, Bae and Chwa [3] recently proved that the total complexity of the farthest-site ((n - 1)st-order) geodesic Voronoi diagram and the number of faces in the diagram are Theta(nc) and Theta(nh), respectively. It is of high interest to know what happens between the first-order and the (n - 1)st-order geodesic Voronoi diagrams. In this paper we prove that the total complexity of the kth-order geodesic Voronoi diagram is Theta(k (n - k) + kc), and the number of faces in the diagram is Theta(k (n - k) + kh). Our results successfully explain the variation from the nearest-site to the farthest-site geodesic Voronoi diagrams, i.e., from k = 1 to k = n - 1, and also illustrate the formation of a disconnected Voronoi region, which does not occur in many commonly used distance metrics, such as the Euclidean, L-1, and city metrics. We show that the kth -order geodesic Voronoi diagram can be computed in O (k(2) (n + c) log(n + c)) time using an iterative algorithm.