An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism

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 2 O(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.

We also describe a deterministic algorithm for constructing the k-level of n lines in two dimensions in O(n log n + nk 1/3 ) time, and constructing the k-level of n planes in three dimensions in O(n log n + nk 3/2 ) time. These time bounds (ignoring the n log n term) match the current best upper bounds on the combinatorial complexity of the k-level. Previously, the same time bound in two dimensions was obtained by Chan (1999) but with randomization.