Vertex deletion for 3D Delaunay triangulations

K. Buchin, O. Devillers, W. Mulzer, O.J. Schrijvers, J. Shewchuk

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


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). Experiments show that our approach is significantly faster than existing implementations if q has high degree, and competitive if q has low degree.
Original languageEnglish
Title of host publicationAlgorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)
EditorsH.L. Bodlaender, G.F. Italiano
Place of PublicationBerlin
ISBN (Print)978-3-642-40449-8
Publication statusPublished - 2013
Event21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France
Duration: 2 Sept 20134 Sept 2013
Conference number: 21st

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference21st Annual European Symposium on Algorithms (ESA 2013)
Abbreviated titleESA 2013
CitySophia Antipolis
Internet address


Dive into the research topics of 'Vertex deletion for 3D Delaunay triangulations'. Together they form a unique fingerprint.

Cite this