### 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 | |

Publication status | Published - 2013 |

Event | 21st Annual European Symposium on Algorithms (ESA 2013) - Sophia Antipolis, France Duration: 2 Sep 2013 → 4 Sep 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 | France |

City | Sophia Antipolis |

Period | 2/09/13 → 4/09/13 |

Internet address |

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

## 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