Fast Delaunay Triangulation for Converging Point Relocation Sequences

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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. Experiments show 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 several times faster than rebuilding.
Type de document :
Communication dans un congrès
European Workshop on Computational Geometry, 2009, Bruxelles, Belgium. 2009
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00413351
Contributeur : Pedro Machado Manhaes de Castro <>
Soumis le : jeudi 3 septembre 2009 - 18:16:00
Dernière modification le : samedi 27 janvier 2018 - 01:31:33
Document(s) archivé(s) le : mardi 15 juin 2010 - 23:10:58

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00413351, version 1

Collections

Citation

Pedro Machado Manhães de Castro, Olivier Devillers. Fast Delaunay Triangulation for Converging Point Relocation Sequences. European Workshop on Computational Geometry, 2009, Bruxelles, Belgium. 2009. 〈inria-00413351〉

Partager

Métriques

Consultations de la notice

292

Téléchargements de fichiers

123