Linear-time Delaunay triangulations simplified

K. Buchin, W. Mulzer

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

50 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.
Originele taal-2Engels
TitelAbstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)
StatusGepubliceerd - 2009

Vingerafdruk Duik in de onderzoeksthema's van 'Linear-time Delaunay triangulations simplified'. Samen vormen ze een unieke vingerafdruk.

Citeer dit