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/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

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 two variants of BrioDC, an algorithm that is known to achieve this bound. We implement the first O(n)-time algorithm for constructing Delaunay triangulations and found that our implementations are practical. While we do not improve upon fast existing algorithms (with non-optimal worst-case running time) for realistic data sets, our BrioDC implementations do give us insight into the optimal time needed for point location. Secondly, we implement and evaluate variants of BRIO, an algorithm which has an O(n log n) worst-case running time on small integers but runs faster for many distributions. Our variants aim to avoid bad worst-case behavior, which is due to high point location time. Our BrioDC implementation shows that point location time can be reduced by 25% and our squarified space-filling curve orders show the first improvement by reducing this by 3%. Keywords: Delaunay triangulations; algorithm engineering; word RAM
Originele taal-2Engels
Titel10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD'13), 8-10 July 2013 St.Petersburg, Russia
Plaats van productiePiscataway
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's7-15
ISBN van geprinte versie978-0-7695-5037-4
DOI's
StatusGepubliceerd - 2013
Evenementconference; 10th International Symposium on Voronoi Diagrams in Science and Engineering; 2013-07-08; 2013-07-10 -
Duur: 8 jul 201310 jul 2013

Congres

Congresconference; 10th International Symposium on Voronoi Diagrams in Science and Engineering; 2013-07-08; 2013-07-10
Periode8/07/1310/07/13
Ander10th International Symposium on Voronoi Diagrams in Science and Engineering

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

    Schrijvers, O. J., Bommel, van, F., & Buchin, K. (2013). Delaunay triangulations on the word RAM : towards a practical worst-case optimal algorithm. In 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD'13), 8-10 July 2013 St.Petersburg, Russia (blz. 7-15). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISVD.2013.10