|
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},
}
|
 |