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 metadatas


https://hal.inria.fr/hal-00963520
Contributor : Olivier Devillers <>
Submitted on : Friday, March 21, 2014 - 2:34:55 PM
Last modification on : Wednesday, August 7, 2019 - 12:19:22 PM
Long-term archiving on : Saturday, June 21, 2014 - 11:46:16 AM

Files

poster.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00963520, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

327

Files downloads

443