Delaunay triangulations on the word RAM: towards a practical worst-case optimal algorithm

O.J. Schrijvers, F. Bommel, van, K. Buchin

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

95 Downloads (Pure)

Samenvatting

The Delaunay triangulation of n points in the plane can be constructed in o(n log n) time when the coordinates of the points are integers from a restricted range. However, algorithms that are known to achieve such running times had not been implemented so far. We explore ways to obtain a practical algorithm for Delaunay triangulations in the plane that runs in linear time for small integers. For this, we first implement and evaluate variants of an algorithm, BrioDC, that is known to achieve this bound. We find that our implementations of these algorithms are competitive with fast existing algorithms. Secondly, we implement and evaluate variants of an algorithm, BRIO, that runs fast in experiments. Our variants aim to avoid bad worst-case behavior and our squarified orders indeed provide faster point location.
Originele taal-2Engels
TitelAbstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012)
Plaats van productiePerugia
UitgeverijUniversità degli Studi di Perugia
Pagina's13-16
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Delaunay triangulations on the word RAM: towards a practical worst-case optimal algorithm'. Samen vormen ze een unieke vingerafdruk.

Citeer dit