# Title: An Optimal Algorithm for Higher-Order Voronoi Diagrams in
the Plane

## Speaker: Timothy Chan, University of Illinois at Urbana-Champaign

## Date and time: 2pm (New York time), Tuesday, October 24, 2023

## Place: On Zoom (details provided on the seminar mailing list)

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.