The order-$k$ Voronoi diagram is a classic geometric structure, which has been studied since the early days of computational geometry in the 70s and 80s. In this talk, I will 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 + k)$, which improves the previous, two-decades-old result of Ramos (SoCG'99) by a $2^{O(\log^*k)}$ factor. The solution consists of two parts: first, we use a decision-tree technique of Chan and Zheng (SODA'22) to reduce the problem to verifying an order-$k$ Voronoi diagram; second, we solve the verification problem by a divide-and-conquer algorithm using planar-graph separators.
This is joint work with Pingan Cheng (Aarhus U.) and Da Wei Zheng (UIUC), to appear in SODA 2024.