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. )
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.
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.
The image nearby shows the enumerate control panel. The controls have the following effects:
triangulation: VB = 3 VI = 1 no flaps tri. v1 v2 v3 0: 0 1 2 1: 0 1 3 2: 0 2 3 Vertices: 0: 300 300 <--- coordinates of vertex 0 1: 541 300 <--- coordinates of vertex 1 2: 180 500 <--- coordinates of vertex 2 3: 180 100 <--- coordinates of vertex 3 3 boundary edges: 0: 1 2 <--- vertices of boundary edge 0 1: 1 3 <--- vertices of boundary edge 1 2: 2 3 <--- vertices of boundary edge 2 3 interior edges: 0: 0 1 <--- vertices of interior edge 0 1: 0 2 <--- vertices of interior edge 1 2: 0 3 <--- vertices of interior edge 2 3 boundary vertices: 0: 1 3 --- 2 3 <--- boundary vertex 0 has index 1, degree 3, neighboring vertices have indices 2 and 3 1: 2 3 --- 1 3 <--- boundary vertex 1 has index 2, degree 3, neighboring vertices have indices 1 and 3 2: 3 3 --- 1 2 <--- boundary vertex 2 has index 3, degree 3, neighboring vertices have indices 1 and 2 1 interior vertices: 0: 0 3 <--- interior vertex 0 has degree 0 and degree 3
counting all 46281 triangulations (44669 have flaps) Number of triangulations: VB = 3 4 5 6 7 8 9 10 11 12 13 14 VI 0 1 1 1 3 4 12 27 78 214 654 1,944 5,767 1 1 2 4 11 28 90 285 951 3,198 10,938 2 1 5 14 53 178 673 2,461 9,280 3 4 18 69 293 1,187 4,919 4 16 88 396 1,845 5 78 489 Number of Triangles: 1 1 2 1 3 2 4 5 5 9 6 28 7 73 8 239 9 762 10 2,659 11 9,264 12 33,238Thus 44,669 of the 46,281 triangulations have flaps, there are 2,659 triangulations with exactly 10 triangles, and there are 4,919 triangulations with 9 boundary vertices and 3 interior vertices.
not counting 44669 triangulations with flaps Number of triangulations: VB = 3 4 5 6 7 8 9 10 11 12 13 14 VI 0 1 1 1 1 1 1 1 1 1 1 1 2 1 3 4 8 12 23 39 75 3 4 10 22 53 119 279 4 16 50 135 393 5 78 278 Number of Triangles: 1 2 3 1 4 1 5 2 6 4 7 9 8 19 9 51 10 127 11 372 12 1,026Thus there are for example 75 different triangulations with 2 interior vertices, 10 boundary vertices, and no flaps.
It is possible to download files form our server directly into the MDS code running on your machine, using the menu in row 5. The following files are currently available:
The entire package, containing all class files and triangulation lists, can be obtained by downlaoding the file
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.
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.
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:
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.
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.
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 |
This chapter is under construction.
[31-Jan-2003]