Skip to Main content Skip to Navigation
Poster communications

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 :
Poster communications
Complete list of metadata
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Friday, March 21, 2014 - 2:34:55 PM
Last modification on : Friday, January 21, 2022 - 3:10:17 AM
Long-term archiving on: : Saturday, June 21, 2014 - 11:46:16 AM


Files produced by the author(s)


  • HAL Id : hal-00963520, version 1



Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers, Jonathan Shewchuk. Vertex Deletion for 3D Delaunay Triangulations. ACM. Symposium on Theory of Computing, 2013, Palo Alto, United States. 2013. ⟨hal-00963520⟩



Les métriques sont temporairement indisponibles