Delaunay Triangulations for Moving Points
Résumé
This paper considers the problem of updating efficiently a Delaunay triangulation when vertices are moving under small perturbations. Its main contribution is a set of algorithms based on the concept of vertex tolerance. Experiment shows that it is able to outperform the naive rebuilding algorithm in certain conditions. For instance, when points, in two dimensions, are relocated by Lloyd's iterations, our algorithm performs about several times faster than rebuilding.
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)