Vertex deletion for 3D Delaunay triangulations

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelAlgorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)
RedacteurenH.L. Bodlaender, G.F. Italiano
Plaats van productieBerlin
UitgeverijSpringer
Pagina's253-264
ISBN van geprinte versie978-3-642-40449-8
DOI's
StatusGepubliceerd - 2013
Evenement21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, Frankrijk
Duur: 2 sep 20134 sep 2013
Congresnummer: 21st
http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Publicatie series

NaamLecture Notes in Computer Science
Volume8125
ISSN van geprinte versie0302-9743

Congres

Congres21st Annual European Symposium on Algorithms (ESA 2013)
Verkorte titelESA 2013
LandFrankrijk
StadSophia Antipolis
Periode2/09/134/09/13
Ander21st Annual European Symposium on Algorithms
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Vertex deletion for 3D Delaunay triangulations'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K., Devillers, O., Mulzer, W., Schrijvers, O. J., & Shewchuk, J. (2013). Vertex deletion for 3D Delaunay triangulations. In H. L. Bodlaender, & G. F. Italiano (editors), Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings) (blz. 253-264). (Lecture Notes in Computer Science; Vol. 8125). Springer. https://doi.org/10.1007/978-3-642-40450-4_22