Fast (O (nlogn)) Delaunay Limited Triangulation Algorithms

Question

Does anyone know any algorithms (link to a research article, if you know) that create limited delayed triangulation in O (nlogn) and any algorithms that allow you to exclude and add constraints and vertices that do not require re-calculation total CDT?

Answer 1

Chew 1989 introduces an algorithm O(nlogn)for generating CDT, as well as Sloan 1992 . I find Sloan's algorithm easier, but your mileage may vary.

For dynamic updates, the best algorithm I know is presented by Kallmann et al . IIRC their algorithm is quite sensitive to the number of constraints, and therefore not suitable for, for example, pathfinding in a world like Minecraft, where the constraint space is large and very dynamic.

All of these documents cover two-dimensional spaces; if you want this in 3D, I suspect you will have to do some original research. In any case, good luck.