Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : The theoretical complexity of vertex removal in a Delaunay triangulation is often given in terms of the degree d of the removed point, with usual results O(d), O(d log d), or O(d²). In fact, the asymptotic complexity is of poor interest since d is usually quite small. In this paper we carefully design code for small degrees 3≤ d≤ 7, it improves the global behavior of the removal for random points by more than 45%.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2011, 44, pp.169-177. 〈10.1016/j.comgeo.2010.10.001〉
Liste complète des métadonnées

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


https://hal.inria.fr/inria-00560379
Contributeur : Olivier Devillers <>
Soumis le : vendredi 28 janvier 2011 - 11:15:11
Dernière modification le : samedi 27 janvier 2018 - 01:31:40
Document(s) archivé(s) le : mardi 6 novembre 2012 - 12:30:59

Fichiers

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

Identifiants

Collections

Citation

Olivier Devillers. Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization. Computational Geometry, Elsevier, 2011, 44, pp.169-177. 〈10.1016/j.comgeo.2010.10.001〉. 〈inria-00560379〉

Partager

Métriques

Consultations de la notice

316

Téléchargements de fichiers

542