Talk in NYU CG seminar, 10/24/2023.

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.