Linear-time Delaunay triangulations simplified

K. Buchin, W. Mulzer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

64 Downloads (Pure)


Recently it was shown that — under reasonable assumptions— Voronoi diagrams and Delaunay triangulations of planar point sets can be computed in time o(n log n), beating the classical comparisonbased lower bound. A number of increasingly faster randomized algorithms have been proposed, most recently a linear-time algorithm based on a randomized incremental construction that uses a combination of nearest neighbor graphs and the history structure to speed up point location. We present a simpler variant of this approach relying only on nearest neighbor graphs. The algorithm and its analysis generalize to higher dimensions, with an expected performance that is proportional to the structural change of the randomized incremental construction. As a byproduct, we analyze an interesting class of insertion orders for randomized incremental constructions.
Original languageEnglish
Title of host publicationAbstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)
Publication statusPublished - 2009


Dive into the research topics of 'Linear-time Delaunay triangulations simplified'. Together they form a unique fingerprint.

Cite this