A Constrained Two-Dimensional Triangulation and the Solution of Closest Node Problems in the Presence of Barriers

A Delaunay triangulation of a set of nodes is a collection of triangles whose vertices are at the nodes and whose union fills the convex hull of the set of nodes. It also has several geometrical properties, making it useful for solving closest point problems. The generalization presented here allows the triangulation to cover nonconvex regions including those with holes. Although a variety of such generalizations are possible, the one presented here is shown to retain important closest point characteristics. Thus it is useful for determining shortest paths within planar regions with polygonal boundaries.