Peter Alfeld Department of Mathematics College of Science University of Utah
The Bernstein Bézier Form Home Page Examples
Spline Spaces and Minimal Determining Sets    User's Guide Residual Arithmetic
Triangulations How does it work?    Bibliography

Triangulations

A Triangulation T is a collection of N triangles satisfying the following requirements:

  1. The interiors of the triangles are pairwise disjoint.
  2. Each edge of a triangle in T is either a common edge of two triangles in T or else it is on the boundary of the union D of all the triangles.
  3. D is homeomorphic to a square

The first requirement says that triangles don't overlap. The second requirement rules out combinations of triangles where one has a vertex in the interior of an edge of another triangle, and the strange sounding last requirement rules out holes, pinchpoints (where just 2 triangles meet in a single point) and disjoint sets of triangles.

The reason for the popularity of triangulations is that given any set of points, one can construct a triangulation that has those points as the vertices of the triangulation. Triangulations are a natural generalization of the concept of partitioning an interval into subintervals.

The Figure nearby illustrates a triangulation. The vertices are indicated by circles, and the triangles by grey shading. The domain D of interest therefore is the grey polygon. The triangulation consists of 16 triangles that share 14 vertices, 10 of which lie on the boundary of D .

To facilitate discussions we have to introduce some notation and language:

Notes

Triangulations form a huge subject in Mathematics. You may be interested in looking at these two very different graduate level books in Computer Science and Mathematics, respectively:

To whet your appetite, here is a description of just one aspect of triangulations. It is possible to build any triangulation T by starting with a single triangle and then adding one triangle at a time, joining it to the growing triangulation either on one or on two boundary edges, such that at every stage one continues to have a triangulation. This may seem obvious but in fact a similar statement does not hold for triangulations in three dimension (where one uses tetrahedra instead of triangles). Click here to see a counterexample.
[15-Mar-1999]