HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [28 references]  Display  Hide  Download

Contributor : Pedro Machado Manhaes de Castro Connect in order to contact the contributor
Submitted on : Thursday, September 3, 2009 - 5:56:14 PM
Last modification on : Thursday, January 20, 2022 - 4:13:44 PM
Long-term archiving on: : Tuesday, October 16, 2012 - 10:16:28 AM


Files produced by the author(s)




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⟩



Record views


Files downloads