Delaunay Triangulations for Moving Points

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Type de document :
Rapport
[Research Report] RR-6750, INRIA. 2008
Liste complète des métadonnées

https://hal.inria.fr/inria-00344053
Contributeur : Pedro Machado Manhaes de Castro <>
Soumis le : mercredi 3 décembre 2008 - 15:13:28
Dernière modification le : lundi 28 mai 2018 - 15:38:02
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:42:33

Fichier

RR-6750.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00344053, version 1

Collections

Citation

Pedro Machado Manhães de Castro, Olivier Devillers. Delaunay Triangulations for Moving Points. [Research Report] RR-6750, INRIA. 2008. 〈inria-00344053〉

Partager

Métriques

Consultations de la notice

414

Téléchargements de fichiers

372