Delaunay triangulations in O(sort(n)) time and more

Wolfgang Mulzer

Voronoi diagrams and Delaunay triangulations are among the most basic structures in computational geometry, and have been discovered and rediscovered several times. Many algorithms have been developed to compute Delaunay triangulations and Voronoi diagrams in O(n log n) time, and have been shown to be optimal in a comparison-based model of computation with infinite precision. Actual computers, however, offer only finite precision and allow arbitrary bit manipulation in constant time.

I will show that by using the word RAM, a model which accounts for finite precision and bit manipulation, the Delaunay triangulation can actually be found in time O(n (log log n)1/2). The result is based on a combination of classic techniques from previous heuristics with a new variant of the randomized incremental construction paradigm that uses dependent sampling.

I will also discuss extensions to higher dimensions, and how we can use our techniques for faster Delaunay triangulation of presorted point sets and of subsets from polynomial size universes. I will also talk about how our techniques apply to convex hulls in three dimensions.

Joint work with Kevin Buchin (TU Eindhoven).