Carleton University - School of Computer Science Honours Project
Winter 2020
Overview of Delaunay Triangulation Algorithms
Bence Meszaros
SCS Honours Project Image
ABSTRACT
In this paper, we motivate a type of point-set triangulation which maximizes minimum angles, called a Delaunay triangulation, implement two Delaunay triangulation algorithms in the Rust language, benchmark six total Delaunay triangulation algorithms, and compare their performance on five datasets of varying distributions, to test the robustness of each algorithm, the overhead associated with running them, as well as their ability to scale. We introduce some computational geometric results related to triangulation, discuss each algorithm briefly, and discuss testing and benchmarking methodologies and results. We conclude that the highly tuned, modern triangulation library Delaunator performs the best overall, but that a naive algorithm performs surprisingly well for small inputs. Source code is included to reproduce results, as well as setup and running instructions in the appendixes.