A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations

Ohio State University, Oct 31, 2012

Voronoi diagrams and their duals, Delaunay triangulations, are used in many areas of computing and the sciences.
Starting in 3-dimensions, there is a substantial (i.e. polynomial) difference between the best case and the worst case complexity of these objects when starting with $n$ points.
This motivates the search for algorithms that are output-senstiive rather than relying only on worst-case guarantees.
In this talk, I will describe a simple, new algorithm for computing Voronoi diagrams in $d$-dimensions that runs in $O(f \log n \log \Delta)$ time, where $f$ is the output size and the spread $\Delta$ of the input points is the ratio of the diameter to the closest pair distance.
For a wide range of inputs, this is the best known algorithm.
The algorithm is novel in the that it turns the classic algorithm of Delaunay refinement for mesh generation on its head, working backwards from a quality mesh to the Delaunay triangulation of the input.
Along the way, we will see instances of several other classic problems for which no higher-dimensional results are known, including kinetic convex hulls and splitting Delaunay triangulations.