Cells

Note, this page describes work in progress!

Clicking on the button labeled cells on the Control panel brings up the Cell Control Panel. This page describes that panel.

A cell is a configuration with one interior vertex such that all tetrahedra share that vertex. Cells are interesting in their own right, but they are particularly important because understanding the dimension of spline spaces on cells for all values of d would make it possible to determine the dimension of spline spaces on general configurations for d sufficiently large.

The cell package produces abstract configurations which are lists of 4-tuples representing tetrahedra. The elements of the four tuple represent points (usually on the sphere), and a particular assignment of coordinates to these points define a configuration, a particular realization of that particular abstract configuration.

An (abstract) configuration is equivalent to an (abstract) triangulation of the sphere. Associated with each vertex of that triangulation is its degree. We also associate with each vertex the sequence of degrees of its neighboring vertices traversed in order. Such degree sequences are equivalent if they are identical after possibly changing the starting vertex and reversing the direction of the sequence.

The package considers several levels of sameness of two cells:

The two cells have the same numbers of boundary vertices.
The two cells have the same number of vertices for each degree. Thus the histograms of the degrees are identical.
The two cells have identical sets of degree sequences.
One abstract configuration can be obtained from the other by relabeling the vertices and permuting the list of tetrahedra.
One configuration can be obtained from the other by an affine transformation of the locations of the vertices.

The cell package is currently unable to check for sameness 4. It does recognize sameness 3. Interestingly, no configuration has yet been found that has sameness 2 but not sameness 3. Any such configuration would have to have at least 20 boundary vertices. It would be remarkable if sameness 2 implied sameness 3, and it would be interesting to find a proof or a counter example.

The following table lists the number of cells of sameness 1 (but not sameness 2) where V is the total number of boundary vertices (excluding the interior vertex). In constructing this table the package considers two cells equivalent if they have sameness 3. Using instead sameness 4 would increase the numbers of cells for a given value of V.

V: 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

number of cells: 1 1 2 5 13 33 85 199 437 936 1,878 3,674 6,910 12,638 22,536

The Cell Control Panel

Row 1:
- The status field indicates certain conditions, in particular:
  - no cells loaded Currently the only cell known to the system is the Clough-Tocher split.
  - area OK The realization is considered a triangulation of the unit sphere, and the areas of the spherical triangles add to 4 pi.
  - bad area The areas of the spherical triangles add to the given value which is distinct from 4 pi. Unfortunately the current realization algorithm works poorly, and this error may occur.
Row 2:
- Hide causes the Cell Control Window to disappear. To make it reappear click on cells in the main control panel.
- Load loads all cells with up to as many boundary vertices as given in the adjacent menu. These abstract cells have been recomputed and are downloaded from the net. Downloading sets with a large number of vertices can take a substantial amount of time. The largest file, of cells with up to 18 boundary vertices has a size of 388 megaBytes.
- The menu let's you choose the number of boundary vertices of the cell. This is equivalent to choosing the number of vertices in the corresponding triangulation of a sphere. (The total number of vertices includes the interior vertex of the cell.)
- The text field row lets you specify the index number of the desired cell. The green buttons scroll up and down in the list. The red buttons do the same, but also display each new cell.
- Show causes the cell to be realized and drawn.
Row 3: The controls in this row let you select certain cells, by specifying minimum and maximum degrees and minimum and maximum numbers of vertices.
- The first text field and its scroll buttons determine the minimum degree you want each vertex to have. The second text field determines the maximum degree. Clicking on the yellow button toggles between "inclusive" where the minimum and maximum degrees need not be assumed, and "sharp where vertices of the specified minimum and maxim degrees must actually be present.
- The third and fourth text fields specify the minimum and maximum number of vertices (on the surface) that you want your configuration to have.
Row 4:
- Report causes a description of the cell to be printed to standard output.
- The remaining items in the fourth row can be used to modify the realization of the cell, as follows:
  - nice decreases the areas of the large boundary triangles to provide a more balanced look.
  - center computes the average of the boundary points, makes this the new center of the sphere, and renormalizes the boundary points.
  - reset restores the original realization.
  - The region surrounding a particular boundary vertex can be enlarged by entering the index of that vertex in the text field. The center of the sphere is moved halfway towards that vertex, and then the location of all vertices is renormalizes.

Vertex Splitting

The cells are constructed using the technique of vertex splitting. A new cell is spawned by splitting one vertex of the parent cell. All cells can be constructed in this way starting with the Clough-Tocher split.

Examples

The original cell (cell 0) is described by this report:

4 triangles: 
0: 1 2 3
1: 2 3 4
2: 1 3 4
3: 1 2 4
5 vertices: 
0: 4
1: 3 - 0 -> 3(2) 3(3) 3(4) 
2: 3 - 0 -> 3(1) 3(3) 3(4) 
3: 3 - 0 -> 3(1) 3(2) 3(4) 
4: 3 - 0 -> 3(2) 3(3) 3(1) 
Points:
0: 0.0 0.0 0.0 ... 0.0
1: 0.0 0.0 1.0 ... 1.0
2: 0.866 0.0 -0.4999 ... 1.0
3: -0.433 0.75 -0.4999 ... 1.0
4: -0.433 -0.7499 -0.4999 ... 1.0
areas:
0: 1 2 3 3.5218
1: 2 3 4 2.0008
2: 1 3 4 3.5218
3: 1 2 4 3.5218
 total area = 12.5663

The interior point (always) has index 0, and there are four boundary points labeled 1, 2, 3, 4. There are four boundary triangles whose vertices are defined by the listed indices. There is a total of 5 vertices. The interior vertex, 0, has degree 4. The boundary vertices all have degree 3. They all have degree sequences 3-3-3. The numbers in parentheses indicate the indices of the actual neighbors. The numbers enclosed by - and -> (in this case all zeros) are codes that identify the degree sequence The coordinates of the points and their norms are given. The areas of the individual spherical triangles, and the sum of these areas are also listed.

Cell 1 is obtained by splitting vertex 1:


6 triangles: 
0: 2 3 5
1: 2 3 4
2: 1 3 4
3: 1 2 4
4: 1 2 5
5: 1 3 5
6 vertices: 
0: 5
4: 3 - 7 -> 4(2) 4(3) 4(1) 
5: 3 - 7 -> 4(2) 4(3) 4(1) 
1: 4 - 5 -> 4(3) 3(4) 4(2) 3(5) 
2: 4 - 5 -> 4(3) 3(5) 4(1) 3(4) 
3: 4 - 5 -> 4(2) 3(5) 4(1) 3(4) 
Points:
0: 0.0 0.0 0.0 ... 0.0
1: -0.25 -0.433 0.866 ... 1.0
2: 0.866 0.0 -0.4999 ... 1.0
3: -0.433 0.75 -0.4999 ... 1.0
4: -0.433 -0.7499 -0.4999 ... 1.0
5: 0.25 0.433 0.866 ... 1.0
areas:
0: 2 3 5 2.2604
1: 2 3 4 2.0008
2: 1 3 4 2.5575
3: 1 2 4 2.5575
4: 1 2 5 1.595
5: 1 3 5 1.595
 total area = 12.5663
 splitting history: 
0 1: 2 3 2 3 4

Thus vertex 1 is split into vertex 1 and the new vertex 5, and neighbors 2 and 3 of the old vertex 1 are now attached to both vertex 1 and 5.

The splitting history described how this cell was obtained from the original cell. The given numbers indicate:

0: index of the split, starting at 0.
1: index of the vertex that is being split.
2: number k of edges being attached to the new vertex. The first and last of these are attached to both the old and new vertex.
3: degree of the old vertex prior to splitting.
The next k numbers are the indices (in order) of the vertices attached to the new vertex.
The remaining numbers are the indices of the vertices attached (only) to the old vertex.

Cell 2 is obtained by splitting vertex 1 twice, and is the asymmetric 8-cell (with 8 tetrahedra):

8 triangles: 
0: 2 3 5
1: 2 3 4
2: 3 4 6
3: 1 2 4
4: 1 2 5
5: 1 3 5
6: 1 3 6
7: 1 4 6
7 vertices: 
0: 6
5: 3 - 17 -> 4(2) 5(3) 5(1) 
6: 3 - 17 -> 5(3) 4(4) 5(1) 
2: 4 - 23 -> 5(3) 3(5) 5(1) 4(4) 
4: 4 - 23 -> 4(2) 5(3) 3(6) 5(1) 
1: 5 - 38 -> 4(2) 4(4) 3(6) 5(3) 3(5) 
3: 5 - 38 -> 4(2) 3(5) 5(1) 3(6) 4(4) 
Points:
0: 0.0 0.0 0.0 ... 0.0
1: 0.0019 -0.3915 0.9201 ... 1.0
2: 0.866 0.0 -0.4999 ... 1.0
3: -0.433 0.75 -0.4999 ... 1.0
4: -0.433 -0.7499 -0.4999 ... 1.0
5: 0.25 0.433 0.866 ... 1.0
6: -0.4849 -0.4449 0.7528 ... 0.9999
areas:
0: 2 3 5 2.2604
1: 2 3 4 2.0008
2: 3 4 6 2.009
3: 1 2 4 2.5726
4: 1 2 5 1.2507
5: 1 3 5 1.1831
6: 1 3 6 0.8861
7: 1 4 6 0.4033
 total area = 12.5663
 splitting history: 
0 1: 2 3 2 3 4
1 1: 2 4 3 4 2 5

Cell 3 is the Octahedron. Vertex 1 is split twice, but the second time three of its neighbors are attached to the new vertex. Two of those, and the remaining neighbor, are attached to the old vertex.

8 triangles: 
0: 2 3 5
1: 2 3 4
2: 1 3 4
3: 2 4 6
4: 2 5 6
5: 1 3 5
6: 1 4 6
7: 1 5 6
7 vertices: 
0: 6
1: 4 - 15 -> 4(3) 4(4) 4(6) 4(5) 
2: 4 - 15 -> 4(3) 4(5) 4(6) 4(4) 
3: 4 - 15 -> 4(2) 4(5) 4(1) 4(4) 
4: 4 - 15 -> 4(2) 4(3) 4(1) 4(6) 
5: 4 - 15 -> 4(2) 4(3) 4(1) 4(6) 
6: 4 - 15 -> 4(2) 4(4) 4(1) 4(5) 
Points:
0: 0.0 0.0 0.0 ... 0.0
1: -0.4656 -0.2888 0.8365 ... 0.9999
2: 0.866 0.0 -0.4999 ... 1.0
3: -0.433 0.75 -0.4999 ... 1.0
4: -0.433 -0.7499 -0.4999 ... 1.0
5: 0.25 0.433 0.866 ... 1.0
6: -0.0173 -0.5476 0.8365 ... 1.0
areas:
0: 2 3 5 2.2604
1: 2 3 4 2.0008
2: 1 3 4 2.2224
3: 2 4 6 2.2224
4: 2 5 6 1.5165
5: 1 3 5 1.5165
6: 1 4 6 0.5235
7: 1 5 6 0.3034
 total area = 12.5663
 splitting history: 
0 1: 2 3 2 3 4
1 1: 3 4 4 2 5 3

V:	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
number of cells:	1	1	2	5	13	33	85	199	437	936	1,878	3,674	6,910	12,638	22,536