Geometric Tools for Computer Graphics

13.8 DELAUNAY TRIANGULATION

A triangulation of a finite set of points is a set of triangles whose vertices are the points in S and whose edges connect pairs of points in S. Each point of S is required to occur in at least one triangle. The edges are only allowed to intersect at the vertices. An optional requirement is that the union of the triangles is the convex hull of S. Figure 13.42 shows triangulations of two point sets. The triangulation in Figure 13.42(a) includes the optional requirement, but the triangulation in Figure 13.42(b) does not. Similar terminology is used for constructing tetrahedra whose vertices are points in a finite set ...