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

Timothy M. Chan, Pingan Cheng, Da Wei Zheng

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)$, wh…