Vertex deletion for 3D Delaunay triangulations

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

doi:10.1007/978-3-642-40450-4_22

Vertex deletion for 3D Delaunay triangulations

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

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). Experiments show that our approach is significantly faster than existing implementations if q has high degree, and competitive if q has low degree.

Original language	English
Title of host publication	Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)
Editors	H.L. Bodlaender, G.F. Italiano
Place of Publication	Berlin
Publisher	Springer
Pages	253-264
ISBN (Print)	978-3-642-40449-8
DOIs	https://doi.org/10.1007/978-3-642-40450-4_22
Publication status	Published - 2013
Event	21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France Duration: 2 Sept 2013 → 4 Sept 2013 Conference number: 21st http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Publication series

Name	Lecture Notes in Computer Science
Volume	8125
ISSN (Print)	0302-9743

Conference

Conference	21st Annual European Symposium on Algorithms (ESA 2013)
Abbreviated title	ESA 2013
Country/Territory	France
City	Sophia Antipolis
Period	2/09/13 → 4/09/13
Internet address	http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html

Access to Document

10.1007/978-3-642-40450-4_22

Cite this

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 (Eds.), Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings) (pp. 253-264). (Lecture Notes in Computer Science; Vol. 8125). Springer. https://doi.org/10.1007/978-3-642-40450-4_22

@inproceedings{f2716dcc2aa345959ced8489ff8a43ee,

title = "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). Experiments show that our approach is significantly faster than existing implementations if q has high degree, and competitive if q has low degree.",

author = "K. Buchin and O. Devillers and W. Mulzer and O.J. Schrijvers and J. Shewchuk",

year = "2013",

doi = "10.1007/978-3-642-40450-4_22",

language = "English",

isbn = "978-3-642-40449-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "253--264",

editor = "H.L. Bodlaender and G.F. Italiano",

booktitle = "Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)",

address = "Germany",

note = "21st Annual European Symposium on Algorithms (ESA 2013), ESA 2013 ; Conference date: 02-09-2013 Through 04-09-2013",

url = "http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2013.html",

}

Buchin, K, Devillers, O, Mulzer, W, Schrijvers, OJ & Shewchuk, J 2013, Vertex deletion for 3D Delaunay triangulations. in HL Bodlaender & GF Italiano (eds), Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings). Lecture Notes in Computer Science, vol. 8125, Springer, Berlin, pp. 253-264, 21st Annual European Symposium on Algorithms (ESA 2013), Sophia Antipolis, France, 2/09/13. https://doi.org/10.1007/978-3-642-40450-4_22

Vertex deletion for 3D Delaunay triangulations. / Buchin, K.; Devillers, O.; Mulzer, W. et al.
Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings). ed. / H.L. Bodlaender; G.F. Italiano. Berlin: Springer, 2013. p. 253-264 (Lecture Notes in Computer Science; Vol. 8125).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Vertex deletion for 3D Delaunay triangulations

AU - Buchin, K.

AU - Devillers, O.

AU - Mulzer, W.

AU - Schrijvers, O.J.

AU - Shewchuk, J.

N1 - Conference code: 21st

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-40450-4_22

DO - 10.1007/978-3-642-40450-4_22

M3 - Conference contribution

SN - 978-3-642-40449-8

T3 - Lecture Notes in Computer Science

SP - 253

EP - 264

BT - Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings)

A2 - Bodlaender, H.L.

A2 - Italiano, G.F.

PB - Springer

CY - Berlin

T2 - 21st Annual European Symposium on Algorithms (ESA 2013)

Y2 - 2 September 2013 through 4 September 2013

ER -

Buchin K, Devillers O, Mulzer W, Schrijvers OJ, Shewchuk J. Vertex deletion for 3D Delaunay triangulations. In Bodlaender HL, Italiano GF, editors, Algorithms – ESA 2013 (21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings). Berlin: Springer. 2013. p. 253-264. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-40450-4_22

Vertex deletion for 3D Delaunay triangulations

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this