topcomAllTriangulations(Matrix) -- generate all triangulations of a point or vector configuration

Synopsis

Function: topcomAllTriangulations
Usage:

topcomAllTriangulations A

topcomAllTriangulations(A, Homogenize => true, Fine => true, RegularOnly => true)
Inputs:
- A, a matrix,
Optional inputs:
- Homogenize => a Boolean value, default value true
- ConnectedToRegular => a Boolean value, default value true
- Fine => a Boolean value, default value false
- RegularOnly => a Boolean value, default value true
Outputs:
- a list,

Description

This function constructs all triangulations of the point set corresponding to $A$ (or triangulation of the cone over $A$, if Homogenize => false is given). With no optional arguments, the default is to construct all regular triangulations.

A triangulation is a list of lists of the indices of the maximal simplices in the triangulation. (the index of the point corresponding to the $i$-th column (starting at $0$) is simply $i$).

For example, the following point set is the smallest which has a non-regular triangulation. Note that topcomAllTriangulations(Matrix) only generates all the regular triangulations.

i1 : A = transpose matrix {{0,3},{0,1},{-1,-1},{1,-1},{-4,-2},{4,-2}}

o1 = | 0 0 -1 1  -4 4  |
     | 3 1 -1 -1 -2 -2 |

              2       6
o1 : Matrix ZZ  <-- ZZ

i2 : Ts = topcomAllTriangulations A;

i3 : #Ts == 16

o3 = true

i4 : netList Ts

     +---------+---------+---------+---------+---------+---------+---------+
o4 = |{0, 1, 2}|{0, 1, 3}|{0, 2, 4}|{0, 3, 5}|{1, 2, 3}|{2, 3, 4}|{3, 4, 5}|
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 2}|{0, 1, 3}|{0, 2, 4}|{0, 3, 5}|{1, 2, 3}|{2, 3, 5}|{2, 4, 5}|
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 3}|{0, 1, 4}|{0, 3, 5}|{1, 2, 3}|{1, 2, 4}|{2, 3, 4}|{3, 4, 5}|
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 2, 3}|{0, 2, 4}|{0, 3, 5}|{2, 3, 4}|{3, 4, 5}|         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 3, 4}|{0, 3, 5}|{3, 4, 5}|         |         |         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 2, 3}|{0, 2, 4}|{0, 3, 5}|{2, 3, 5}|{2, 4, 5}|         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 3}|{0, 1, 4}|{0, 3, 5}|{1, 3, 4}|{3, 4, 5}|         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 4}|{0, 1, 5}|{1, 2, 3}|{1, 2, 4}|{1, 3, 5}|{2, 3, 4}|{3, 4, 5}|
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 2}|{0, 1, 5}|{0, 2, 4}|{1, 2, 3}|{1, 3, 5}|{2, 3, 5}|{2, 4, 5}|
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 2}|{0, 1, 5}|{0, 2, 4}|{1, 2, 5}|{2, 4, 5}|         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 4}|{0, 1, 5}|{1, 2, 3}|{1, 2, 4}|{1, 3, 5}|{2, 3, 5}|{2, 4, 5}|
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 4}|{0, 1, 5}|{1, 3, 4}|{1, 3, 5}|{3, 4, 5}|         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 2, 4}|{0, 2, 5}|{2, 4, 5}|         |         |         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 4, 5}|         |         |         |         |         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 4}|{0, 1, 5}|{1, 4, 5}|         |         |         |         |
     +---------+---------+---------+---------+---------+---------+---------+
     |{0, 1, 4}|{0, 1, 5}|{1, 2, 4}|{1, 2, 5}|{2, 4, 5}|         |         |
     +---------+---------+---------+---------+---------+---------+---------+

i5 : tri = Ts#0

o5 = {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3,
     ------------------------------------------------------------------------
     4, 5}}

o5 : List

i6 : topcomIsTriangulation(A, tri)

o6 = true

i7 : topcomIsRegularTriangulation(A, tri)

o7 = true

i8 : topcomRegularTriangulationWeights(A, tri)

      97  47  1
o8 = {--, --, -, 0, 0, 0}
      16  16  8

o8 : List

The following code determines the support of each triangulation, and tallies them. Thus for example, we see that there are 6 regular fine triangulations (fine means that all of the points are begin used).

i9 : tally for tri in Ts list sort unique flatten tri

o9 = Tally{{0, 1, 2, 3, 4, 5} => 6}
           {0, 1, 2, 4, 5} => 2
           {0, 1, 3, 4, 5} => 2
           {0, 1, 4, 5} => 1
           {0, 2, 3, 4, 5} => 2
           {0, 2, 4, 5} => 1
           {0, 3, 4, 5} => 1
           {0, 4, 5} => 1

o9 : Tally

The method that topcom uses depends on the optional arguments Fine, ConnectedToRegular and RegularOnly.

i10 : options topcomAllTriangulations

o10 = OptionTable{ConnectedToRegular => true}
                  Fine => false
                  Homogenize => true
                  RegularOnly => true

o10 : OptionTable

If the optional argument Fine is set to true, then only fine triangulations (i.e. those that involve every column of $A$) will be generated.

i11 : Ts = topcomAllTriangulations(A, Fine => true);

i12 : #Ts == 6

o12 = true

If the optional argument RegularOnly is set to false, but ConnectedToRegular is true, it will generally take less time, as the program doesn't need to check each triangulation to see if it is regular.

i13 : T1s = topcomAllTriangulations(A, RegularOnly => true)

o13 = {{{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3,
      -----------------------------------------------------------------------
      4, 5}}, {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3,
      -----------------------------------------------------------------------
      5}, {2, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 4}, {3,
      -----------------------------------------------------------------------
      4, 5}}, {{0, 3, 4}, {0, 3, 5}, {3, 4, 5}}, {{0, 2, 3}, {0, 2, 4}, {0,
      -----------------------------------------------------------------------
      3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 3,
      -----------------------------------------------------------------------
      4}, {3, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1,
      -----------------------------------------------------------------------
      3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2,
      -----------------------------------------------------------------------
      5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 3, 4}, {1, 3, 5}, {3,
      -----------------------------------------------------------------------
      4, 5}}, {{0, 2, 4}, {0, 2, 5}, {2, 4, 5}}, {{0, 4, 5}}, {{0, 1, 4}, {0,
      -----------------------------------------------------------------------
      1, 5}, {1, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 4}, {1, 2, 5}, {2, 4,
      -----------------------------------------------------------------------
      5}}}

o13 : List

i14 : T2s = topcomAllTriangulations(A, RegularOnly => false)

o14 = {{{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3,
      -----------------------------------------------------------------------
      4, 5}}, {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3,
      -----------------------------------------------------------------------
      5}, {2, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1,
      -----------------------------------------------------------------------
      2, 4}, {2, 3, 4}, {3, 4, 5}}, {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3,
      -----------------------------------------------------------------------
      4}, {3, 4, 5}}, {{0, 3, 4}, {0, 3, 5}, {3, 4, 5}}, {{0, 2, 3}, {0, 2,
      -----------------------------------------------------------------------
      4}, {0, 3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5},
      -----------------------------------------------------------------------
      {1, 3, 4}, {3, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1,
      -----------------------------------------------------------------------
      2, 4}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2,
      -----------------------------------------------------------------------
      4}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4},
      -----------------------------------------------------------------------
      {1, 2, 3}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0,
      -----------------------------------------------------------------------
      2, 4}, {1, 2, 5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2,
      -----------------------------------------------------------------------
      4}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 3, 4},
      -----------------------------------------------------------------------
      {1, 3, 5}, {3, 4, 5}}, {{0, 2, 4}, {0, 2, 5}, {2, 4, 5}}, {{0, 4, 5}},
      -----------------------------------------------------------------------
      {{0, 1, 4}, {0, 1, 5}, {1, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 4},
      -----------------------------------------------------------------------
      {1, 2, 5}, {2, 4, 5}}}

o14 : List

i15 : #T1s

o15 = 16

i16 : #T2s

o16 = 18

The following search yields all triangulations, even those not connected via bistellar flips to regular triangulations.

i17 : T3s = topcomAllTriangulations(A, RegularOnly => false, ConnectedToRegular => false)

o17 = {{{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3,
      -----------------------------------------------------------------------
      4, 5}}, {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3,
      -----------------------------------------------------------------------
      5}, {2, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1,
      -----------------------------------------------------------------------
      3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2,
      -----------------------------------------------------------------------
      5}, {2, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1,
      -----------------------------------------------------------------------
      2, 4}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 3,
      -----------------------------------------------------------------------
      4}, {3, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1,
      -----------------------------------------------------------------------
      3, 5}, {2, 3, 5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 2, 4}, {1, 2,
      -----------------------------------------------------------------------
      5}, {2, 4, 5}}, {{0, 1, 4}, {0, 1, 5}, {1, 3, 4}, {1, 3, 5}, {3, 4,
      -----------------------------------------------------------------------
      5}}, {{0, 1, 4}, {0, 1, 5}, {1, 4, 5}}, {{0, 2, 3}, {0, 2, 4}, {0, 3,
      -----------------------------------------------------------------------
      5}, {2, 3, 4}, {3, 4, 5}}, {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 5},
      -----------------------------------------------------------------------
      {2, 4, 5}}, {{0, 2, 4}, {0, 2, 5}, {2, 4, 5}}, {{0, 3, 4}, {0, 3, 5},
      -----------------------------------------------------------------------
      {3, 4, 5}}, {{0, 4, 5}}}

o17 : List

i18 : #T3s

o18 = 18

Given the list of triangulations, we can query them using other topcom functions. See also Triangulations for other functionality.

i19 : netList Ts

      +---------+---------+---------+---------+---------+---------+---------+
o19 = |{0, 1, 2}|{0, 1, 3}|{0, 2, 4}|{0, 3, 5}|{1, 2, 3}|{2, 3, 4}|{3, 4, 5}|
      +---------+---------+---------+---------+---------+---------+---------+
      |{0, 1, 2}|{0, 1, 3}|{0, 2, 4}|{0, 3, 5}|{1, 2, 3}|{2, 3, 5}|{2, 4, 5}|
      +---------+---------+---------+---------+---------+---------+---------+
      |{0, 1, 3}|{0, 1, 4}|{0, 3, 5}|{1, 2, 3}|{1, 2, 4}|{2, 3, 4}|{3, 4, 5}|
      +---------+---------+---------+---------+---------+---------+---------+
      |{0, 1, 4}|{0, 1, 5}|{1, 2, 3}|{1, 2, 4}|{1, 3, 5}|{2, 3, 4}|{3, 4, 5}|
      +---------+---------+---------+---------+---------+---------+---------+
      |{0, 1, 2}|{0, 1, 5}|{0, 2, 4}|{1, 2, 3}|{1, 3, 5}|{2, 3, 5}|{2, 4, 5}|
      +---------+---------+---------+---------+---------+---------+---------+
      |{0, 1, 4}|{0, 1, 5}|{1, 2, 3}|{1, 2, 4}|{1, 3, 5}|{2, 3, 5}|{2, 4, 5}|
      +---------+---------+---------+---------+---------+---------+---------+

i20 : for tri in Ts list topcomIsTriangulation(A, tri)

o20 = {true, true, true, true, true, true}

o20 : List

i21 : for tri in Ts list topcomIsRegularTriangulation(A, tri)

o21 = {true, true, true, true, true, true}

o21 : List

i22 : for tri in Ts list topcomRegularTriangulationWeights(A, tri)

        97  47  1             87  41    1             157  15  1           
o22 = {{--, --, -, 0, 0, 0}, {--, --, - -, 0, 0, 0}, {---, --, -, 0, 0, 0},
        16  16  8             16  16    8              40   8  4           
      -----------------------------------------------------------------------
       45  19  1             107  9    1             35  13    1
      {--, --, -, 0, 0, 0}, {---, -, - -, 0, 0, 0}, {--, --, - -, 0, 0, 0}}
       16  16  8              40  8    4             16  16    8

o22 : List

Caveat

With no optional arguments, this function returns all regular triangulations, not all triangulations!

Ways to use this method: