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

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

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

88 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationAbstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012)
Place of PublicationPerugia
PublisherUniversità degli Studi di Perugia
Pages13-16
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Delaunay triangulations on the word RAM: towards a practical worst-case optimal algorithm'. Together they form a unique fingerprint.

  • Cite this

    Schrijvers, O. J., Bommel, van, F., & Buchin, K. (2012). Delaunay triangulations on the word RAM: towards a practical worst-case optimal algorithm. In Abstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012) (pp. 13-16). Università degli Studi di Perugia.