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 <>
Submitted on : Thursday, September 3, 2009 - 5:56:14 PM
Last modification on : Monday, December 14, 2020 - 4:46:30 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