Fast segment insertion and incremental construction of constrained Delaunay triangulations

The most commonly implemented method of constructing a constrained Delaunay triangulation (CDT) in the plane is to first construct a Delaunay triangulation, then incrementally insert the input segments one by one. For typical implementations of segment insertion, this method has a Θ(kn2)Θ(kn2) worst-case running time, where n is the number of input vertices and k is the number of input segments.We give a randomized algorithm for inserting a segment into a CDT in expected time linear in the number of edges the segment crosses. We demonstrate with a performance comparison that for segments that cross many edges, our algorithm is faster than gift-wrapping. We also show that a simple algorithm for segment location  , which precedes segment insertion, is fast enough never to be a bottleneck in CDT construction. A result of Agarwal, Arge, and Yi implies that randomized incremental construction of CDTs by our segment insertion algorithm takes expected O(nlog⁡n+nlog2⁡k)O(nlog⁡n+nlog2⁡k) time. We show that this bound is tight by deriving a matching lower bound. Although there are CDT construction algorithms guaranteed to run in O(nlog⁡n)O(nlog⁡n) time, incremental CDT construction is easier to program and competitive in practice.Lastly, we partly extend the analysis (albeit not the linear-time insertion algorithm) to randomized incremental CDT construction in three dimensions.