Skip to Main content Skip to Navigation
Conference papers

Vertex Deletion for 3D Delaunay Triangulations

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 metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Tuesday, June 11, 2013 - 4:57:01 PM
Last modification on : Thursday, January 6, 2022 - 12:14:04 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 7:24:18 PM


Files produced by the author(s)




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⟩



Les métriques sont temporairement indisponibles