Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/997817.997846 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
delaunay triangulation update motion | Chew's second algorithm,Combinatorics,Minimum-weight triangulation,Bowyer–Watson algorithm,Computer science,Theoretical computer science,Triangulation (social science),Constrained Delaunay triangulation,Delaunay triangulation,Ruppert's algorithm,Pitteway triangulation | Conference |
ISBN | Citations | PageRank |
1-58113-885-7 | 21 | 0.97 |
References | Authors | |
27 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leonidas J. Guibas | 1 | 13084 | 1262.73 |
| Daniel Russel | 2 | 38 | 2.17 |