Filtering Relocations on a Delaunay Triangulation

Pedro Machado Manhães de Castro 1 Jane Tournois 1 Pierre Alliez 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.
Document type :
Journal articles
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00413344
Contributor : Pedro Machado Manhaes de Castro <>
Submitted on : Thursday, September 3, 2009 - 5:56:14 PM
Last modification on : Saturday, January 27, 2018 - 1:31:40 AM
Long-term archiving on : Tuesday, October 16, 2012 - 10:16:28 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, Olivier Devillers. Filtering Relocations on a Delaunay Triangulation. Computer Graphics Forum, Wiley, 2009, ⟨10.1111/j.1467-8659.2009.01523.x⟩. ⟨inria-00413344⟩

Share

Metrics

Record views

361

Files downloads

418