Constrained Delaunay triangulations

TLDR

Constrained Delaunay triangulations (CDTs) are triangulations that include specified edges and approximate the Delaunay triangulation, and their properties make them useful for finite‑element methods. The study demonstrates that a CDT can be constructed in optimal O(n log n) time via a divide‑and‑conquer algorithm. The algorithm uses a divide‑and‑conquer strategy to construct the CDT, and the resulting structure supports applications such as motion planning with polygonal obstacles and constrained Euclidean minimum spanning trees. The resulting algorithm achieves the same O(n log n) time as for unconstrained Delaunay triangulations and for arbitrary constrained triangulations.

Abstract

Given a set of n vertices in the plane together with a set of noncrossing edges, the constrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimal Ο(n log n) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (nonDelaunay) triangulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that should make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles in the plane and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.