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:

• 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.
• VB is the number of boundary vertices of T, VI is the number of interior vertices of T, and

V = VB + VI

is the total number of vertices of T.

• Similarly, EB is the number of boundary edges of T, EI is the number of interior edges of T, and

E = EB + EI

is the total number of edges of T.

• It can be shown (this is a good exercise ) that for all triangulations T

VB = EB

E = 2VB + 3VI - 3

N = VB + 2VI - 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:

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]