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


Many Triangulations

The MDS code has an experimental feature that lets you enumerate all triangulations of certain types. For example, the Figure nearby shows all possible triangulations with seven triangles having no flaps. (A flap is a triangle having exactly one interior edge. If you allow flaps there are 73 distinct triangulations with 7 triangles. )

Terms and Concepts

A triangulation has two components: its topology which describe how the triangles are connected, and its geometry which is the specification of the precise location of the vertices.

The enumeration mode of the MDS code attempts to compute all possible topologies of triangulations up to a certain number or size. It also has the ability to generate a particular geometry of each of these triangulations, and then display the triangulation and study spline spaces on them.

The original motivation for introducing this mode is that certain proof techniques require the analysis of a large number of particular triangulations with certain properties, and the first step for using these techniques is the ability to list these triangulations. However, using the enumeration mode one can conduct other interesting investigations as well.

In the context of the MDS code, an abstract triangulation is a set of triples of integers. We think of the integers as (abstract) vertices. Pairs of integers are (abstract) edges, and triples are (abstract) triangles. The order of the vertices in the triples is immaterial. Abstract triangulations are constructed recursively. A single triangle is an abstract triangulation. Given an abstract triangulation T, a new abstract triangulation can be obtained by adding a flap to T, or adding a fill. A flap is a new triangle one of whose edges occurs exactly once in the triangles of T. (I.e., the new triangle joins T on exactly one boundary edge.) The third point of the new triangle is not present in any triangle of T. (As a practical matter, it equals the highest index in T + 1). A fill is a new triangle two of whose edges occur exactly once in the triangles of T, and the third of whose edges does not occur at all among the triangles of T. (Since the two existing edges share a vertex on the new triangle they share the same vertex on the old triangulation.)

Two abstract triangulations S and T are isomorphic if T can be obtained by permuting the sequence of triangles and the labeling of vertices in S.

The MDS code proceeds by starting with a single triangle {0,1,2} and adding flaps and fills to form a growing list that contains all (non-isomorphic) abstract triangulations subject to certain constraints.

Invoking the Enumeration Mode

To use the enumeration features you need to download the MDS code. Select ENUMERATE as the last option of the triangulation menu on the MDS Control Panel.

User's Guide

The image nearby shows the enumerate control panel. The controls have the following effects:

Downloading the Package

The entire package, containing all class files and triangulation lists, can be obtained by downlaoding the file

message

Copy that file to a directory on a Unix system and type

source message
(It's called message because it is also suitable for e-mailing.) The directory containing message will also contain the class and data files.

Constructing the list of triangulations

The algorithm to construct the list of up to N triangulations reflects the fact that in multivariate spline research flaps are trivial. Thus within the constraints given by the size of the available stack (and possibly other constraints imposed on the number of triangles or vertices) fills are made whenever possible and flaps are added only when this is necessary to make fills possible. This principle is illustrated in the list of the first 100 triangulations so generated.

The following description of the algorithm assumes for simplicity that the list of triangulations is constrained only by the available space, i.e., the parameter N.

  1. We are given a stack with N levels labeled from 0 to N-1. The stack is filled with triangulations starting from the bottom (at level 0).
  2. The triangle [0,1,2] is put on the stack, and n = fill = flap = 0
  3. While n < N-1

Determining Isomorphisms

As discussed above, two triangulations are isomorphic if one can be obtained from the other by relabeling the vertices and triangles and changing their sequence. Let S and T be two triangulations. The algorithm to compare them is as follows:

  1. If T and S have different values of VB or VI they are not isomorphic
  2. The vertices of T and S are ordered by increasing degree. If two corresponding vertices have different degrees then S and T are not isomorphic.
  3. Now the real work starts.

In computing all triangulations up to 13 triangles, the last step (involving the stack of triangles) never identified two triangulations as distinct that have not already been recognized as such at this stage. If you find two non-isomorphic triangulations that have passed all tests up to this stage the package will inform you and I'd be very interested to hear from you.

Rendering an Abstract Triangulation

The particular geometries displayed in the plotting windows are obtained by arranging the boundary vertices equally spaced in the proper sequence in a circle and then computing coordinates of interior vertices such that each interior vertex is the average of all vertices connected to it by an edge.

Examples

The following table lists the number of triangulations with a given number of boundary vertices (VB) and interior vertices (VI), and no flaps. Clicking on a link will show a picture of these triangulations. Columns correspond to VB, rows to VI. The values for VI=0 (no triangulations without flaps) and VI=1 (one triangulation for each VB) are not shown.

VI/VB 3 4 5 6 7 8 9 10 11
2 1 3 4 8 12 23 39 75 137
3 4 10 22 53 119 279 645    
4 16 50 135 393 1,067        
5 78 278 902            
6 457                

The following table similarly lists the numbers of triangulations including flaps, with a given value of VB and VI, and up to 13 triangles.

VI/VB 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 1 1 3 4 12 27 78 214 654 1,944 6,055 18,900
1 1 2 4 11 28 90 285 951 3,198 10,938 37,567    
2 1 5 14 53 178 673 2,461 9,280 34,712        
3 4 18 69 293 1,187 4,919 20,108            
4 16 88 396 1,845 8,252                
5 78 489 2,497                    
6 457                        

Literature

This chapter is under construction.

[31-Jan-2003]