Vertex Deletion for 3D Delaunay Triangulations

Kevin Buchin 1 Olivier Devillers 2 Wolfgang Mulzer 3 Okke Schrijvers 4 Jonathan Shewchuk 5
1 Departement of Mathematics and Computer Science
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 Institute of Computer Science
4 Computer Science Department [Stanford]
5 Department of Mathematics [Berkeley]
Abstract : We show how to delete a vertex q from a three-dimensional Delaunay triangulation DT(S) in expected O(C(P)) time, where P is the set of vertices neighboring q in DT(S) and C(P) is an upper bound on the expected number of tetrahedra whose circumspheres enclose q that are created during the randomized incremental construction of DT(P).
Type de document :
Communication dans un congrès
21st European Symposium on Algorithms, 2013, Sophia Antipolis, France. Springer, 8125, pp.253-264, 2013, LNCS
Liste complète des métadonnées

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

vignette.jpg
vignette.jpg
https://hal.inria.fr/hal-00832992
Contributeur : Olivier Devillers <>
Soumis le : mardi 11 juin 2013 - 16:57:01
Dernière modification le : samedi 27 janvier 2018 - 01:31:01
Document(s) archivé(s) le : mardi 4 avril 2017 - 19:24:18

Fichiers

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

Identifiants

  • HAL Id : hal-00832992, version 1

Collections

INRIA

Citation

Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers, Jonathan Shewchuk. Vertex Deletion for 3D Delaunay Triangulations. 21st European Symposium on Algorithms, 2013, Sophia Antipolis, France. Springer, 8125, pp.253-264, 2013, LNCS. 〈hal-00832992〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

481

Téléchargements de fichiers

364

Contact


archive-ouverte@inria.fr