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

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.

Domaines: Géométrie algorithmique [cs.CG]

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