L. Guibas, D. Russel, An Empirical Comparison of Techniques for Updating Delaunay Triangulations, ACM Symp. on Computational Geometry, pp. 170-179, 2004

Abstract:

The computation of Delaunay triangulations from static point sets has been extensively studied in computational geometry. When the points move with known trajectories, kinetic data structures can be used to maintain the triangulation. However, there has been little work so far on how to maintain the triangulation when the points move without explicit motion plans, as in the case of a physical simulation. In this paper we examine how to update Delaunay triangulations after small displacements of the defining points, as might be provided by a physics-based integrator. We have implemented a variety of update algorithms, many new, toward this purpose. We ran these algorithms on a corpus of data sets to provide running time comparisons and determined that updating Delaunay can be significantly faster than recomputing.

Bibtex: 

@inproceedings{gr-ectudt-04,
 author = {Leonidas Guibas and Daniel Russel},
 title = {An empirical comparison of techniques for updating Delaunay triangulations},
 booktitle = {SCG '04: Proceedings of the twentieth annual symposium on Computational geometry},
 year = {2004},
 isbn = {1-58113-885-7},
 pages = {170--179},
 location = {Brooklyn, New York, USA},
 doi = {http://doi.acm.org/10.1145/997817.997846},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }