Vertex Deletion for 3D Delaunay Triangulations

摘要

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.