An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
Timothy M. Chan, Pingan Cheng, Da Wei Zheng · Society for Industrial and Applied Mathematics eBooks · 2024
We present the first optimal randomized algorithm for constructing the order-k Voronoi diagram of n points in two dimensions. The expected running time is O(n log n + nk), which improves the previous, two-decades- old result of Ramos (SoCG’99) by a 2O(log* k) factor. To obtain our result, we (i) use a recent decision-tree technique of Chan and Zheng (SODA’22) in combination with Ramos's cutting construction, to reduce the problem to verifying an order-k Voronoi diagram, and (ii) solve the verification problem by a new divide-and-conquer algorithm using planar-graph separators.