Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations
Jonathan Richard Shewchuk · 2000
I discuss algorithms for constructing constrained Delaunay triangulations (CDTs) in dimensions higher than two.If the CDT of a set of vertices and constraining simplices exists, it can be constructed in (.9 (nv ns) time, where nv is the number of input vertices and ns is the number of output d-simplices.In practice, the running time is likely to be O(n~ + n, logn~) in all but the most pathological cases.The CDT of a star-shaped polytope can be constructed in O(n8 log n~) time, yielding an efficient way to delete a vertex from a CDT.