Filtering Relocations on a Delaunay Triangulation
Loading...
Date
2009
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd
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.
Description
@article{10.1111:j.1467-8659.2009.01523.x,
journal = {Computer Graphics Forum},
title = {{Filtering Relocations on a Delaunay Triangulation}},
author = {Manhaes de Castro, Pedro Machado and Tournois, Jane and Alliez, Pierre and Devillers, Olivier},
year = {2009},
publisher = {The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2009.01523.x}
}