Triangulations

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:

The interiors of the triangles are pairwise disjoint.
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.
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:

T is the triangulation, i.e., the set of triangles.
N is the number of triangles in T
D is the union of the triangles in T (and the domain of the splines of interest in these pages).
A vertex of a triangle in T is a boundary vertex of T if it is contained in the boundary of D, it is an interior vertex otherwise (in which case it is contained in the interior of D).
Similarly, an edge of a triangle in T is a boundary edge of T if it is contained in the boundary of D, it is an interior edge otherwise.
V_B is the number of boundary vertices of T, V_I is the number of interior vertices of T, and

V = V_B + V_I

is the total number of vertices of T.
Similarly, E_B is the number of boundary edges of T, E_I is the number of interior edges of T, and

E = E_B + E_I

is the total number of edges of T.
It can be shown (this is a good exercise ) that for all triangulations T
V_B = E_B

E = 2V_B + 3V_I - 3

N = V_B + 2V_I - 2

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:

Franco P. Preparata and Michael Ian Shamos: Computational Geometry, an Introduction, Springer Verlag, 1985, ISBN 0-387-96131-3.
T.B. Rushing, Topological Embeddings, Academic Press, 1973, ISBN 0-12-603550-4

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]