Fast (O(nlogn)) Constrained Delaunay Triangulation Algorithms

Question

Does anyone know of any algorithms (link to the research paper if you know) that create a Constrained Delaunay Triangulation in O(nlogn) time, and any algorithms that allow for deletion and addition of constraints and vertices that does not require the re computation of the entire CDT?

Answer 1

Chew 1989 presents an O(nlogn) algorithm for CDT generation, as does Sloan 1992. I find Sloan's algorithm easier to follow, but your mileage may vary.

For dynamic updates, the best algorithm I know of is presented by Kallmann et al. IIRC their algorithm is quite sensitive to the number of constraints, and so would not be suitable for e.g. pathfinding in a Minecraft-like world where the space of constraints is both large and highly dynamic.

All these papers cover 2D spaces; if you want it in 3D, I suspect you'll have to do some original research. Either way, best of luck.