Abstracts of the 25th European Workshop on Computational Geometry, pp. 231–234
Research account
Fast Delaunay Triangulation for Converging Point Relocation Sequences
Related publications are listed separately below. The illustrated account describes their shared research context.
Filtering Relocations on a Delaunay Triangulation
Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, Olivier Devillers
Computer Graphics Forum 28(5), pp. 1465–1474
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.
The paper has been presented at SGP’09, and published in Computer Graphics Forum (Special issue 6th Annu. Sympos. Geometry Processing), and can be found here.