### 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 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

Original language | English |
---|---|

Title of host publication | 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD'13), 8-10 July 2013 St.Petersburg, Russia |

Place of Publication | Piscataway |

Publisher | Institute of Electrical and Electronics Engineers |

Pages | 7-15 |

ISBN (Print) | 978-0-7695-5037-4 |

DOIs | |

Publication status | Published - 2013 |

Event | conference; 10th International Symposium on Voronoi Diagrams in Science and Engineering; 2013-07-08; 2013-07-10 - Duration: 8 Jul 2013 → 10 Jul 2013 |

### Conference

Conference | conference; 10th International Symposium on Voronoi Diagrams in Science and Engineering; 2013-07-08; 2013-07-10 |
---|---|

Period | 8/07/13 → 10/07/13 |

Other | 10th International Symposium on Voronoi Diagrams in Science and Engineering |

## 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. (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*(pp. 7-15). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISVD.2013.10