Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

vignette.jpg
vignette.jpg
https://hal.inria.fr/hal-00832992
Contributor : Olivier Devillers <>
Submitted on : Tuesday, June 11, 2013 - 4:57:01 PM
Last modification on : Wednesday, August 7, 2019 - 12:19:22 PM
Document(s) archivé(s) le : Tuesday, April 4, 2017 - 7:24:18 PM

Files

Vignette du document
main.pdf
Files produced by the author(s)

Identifiers

Collections

INRIA

Citation

Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers, Jonathan Shewchuk. Vertex Deletion for 3D Delaunay Triangulations. Proceedings of the 21st European Symposium on Algorithms, 2013, Sophia Antipolis, France. pp.253-264, ⟨10.1007/978-3-642-40450-4_22⟩. ⟨hal-00832992⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

570

Files downloads

913

 

Contact                    Legal Notice                    Personal Data