Macaulay2 » Documentation
Packages » Triangulations :: allTriangulations(Matrix)
next | previous | forward | backward | up | index | toc

allTriangulations(Matrix) -- use topcom to generate all triangulations of a point or vector configuration

Synopsis

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.

This function is a wrapper for the topcom function topcomAllTriangulations, and has the same optional arguments as that function. This function returns a list of Triangulation (missing documentation) 's.

A triangulation is a list of list 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.

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 = allTriangulations A

o2 = {triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3},
     ------------------------------------------------------------------------
     {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4},
     ------------------------------------------------------------------------
     {0, 3, 5}, {1, 2, 3}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 3},
     ------------------------------------------------------------------------
     {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {3, 4, 5}},
     ------------------------------------------------------------------------
     triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 4}, {3, 4, 5}},
     ------------------------------------------------------------------------
     triangulation {{0, 3, 4}, {0, 3, 5}, {3, 4, 5}}, triangulation {{0, 2,
     ------------------------------------------------------------------------
     3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1,
     ------------------------------------------------------------------------
     3}, {0, 1, 4}, {0, 3, 5}, {1, 3, 4}, {3, 4, 5}}, triangulation {{0, 1,
     ------------------------------------------------------------------------
     4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}},
     ------------------------------------------------------------------------
     triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5},
     ------------------------------------------------------------------------
     {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4},
     ------------------------------------------------------------------------
     {1, 2, 5}, {2, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3},
     ------------------------------------------------------------------------
     {1, 2, 4}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 4},
     ------------------------------------------------------------------------
     {0, 1, 5}, {1, 3, 4}, {1, 3, 5}, {3, 4, 5}}, triangulation {{0, 2, 4},
     ------------------------------------------------------------------------
     {0, 2, 5}, {2, 4, 5}}, triangulation {{0, 4, 5}}, triangulation {{0, 1,
     ------------------------------------------------------------------------
     4}, {0, 1, 5}, {1, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2,
     ------------------------------------------------------------------------
     4}, {1, 2, 5}, {2, 4, 5}}}

o2 : List
i3 : #Ts == 16

o3 = true
i4 : netList Ts

     +-------------------------------------------------------------------------------------------+
o4 = |triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}}|
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 5}, {2, 4, 5}}|
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {3, 4, 5}}|
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 4}, {3, 4, 5}}                      |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 3, 4}, {0, 3, 5}, {3, 4, 5}}                                            |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 5}, {2, 4, 5}}                      |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 3, 4}, {3, 4, 5}}                      |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}}|
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}|
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 5}, {2, 4, 5}}                      |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}|
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 3, 4}, {1, 3, 5}, {3, 4, 5}}                      |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 2, 4}, {0, 2, 5}, {2, 4, 5}}                                            |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 4, 5}}                                                                  |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 4, 5}}                                            |
     +-------------------------------------------------------------------------------------------+
     |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 4}, {1, 2, 5}, {2, 4, 5}}                      |
     +-------------------------------------------------------------------------------------------+
i5 : tri = Ts#0

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

o5 : Triangulation
i6 : isWellDefined tri

o6 = true
i7 : isRegularTriangulation tri

o7 = true
i8 : Ts/isRegularTriangulation

o8 = {true, true, true, true, true, true, true, true, true, true, true, true,
     ------------------------------------------------------------------------
     true, true, true, true}

o8 : List
i9 : regularTriangulationWeights tri

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

o9 : 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.

i10 : tally for tri in Ts list sort unique flatten max tri

o10 = 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

o10 : Tally

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

i11 : options allTriangulations

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

o11 : 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.

i12 : Ts = allTriangulations(A, Fine => true);
i13 : #Ts == 6

o13 = 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.

i14 : T1s = allTriangulations(A, RegularOnly => true)

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

o14 : List
i15 : T2s = allTriangulations(A, RegularOnly => false)

o15 = {triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4},
      -----------------------------------------------------------------------
      {0, 3, 5}, {1, 2, 3}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 2},
      -----------------------------------------------------------------------
      {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 3, 4}, {0, 3, 5}, {3, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5}, {2, 3, 5}, {2, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 3, 4}, {3, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4},
      -----------------------------------------------------------------------
      {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3},
      -----------------------------------------------------------------------
      {1, 2, 4}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 2},
      -----------------------------------------------------------------------
      {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 5}, {2, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 3, 4},
      -----------------------------------------------------------------------
      {1, 3, 5}, {3, 4, 5}}, triangulation {{0, 2, 4}, {0, 2, 5}, {2, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 4,
      -----------------------------------------------------------------------
      5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 4}, {1, 2, 5}, {2, 4,
      -----------------------------------------------------------------------
      5}}}

o15 : List
i16 : #T1s

o16 = 16
i17 : #T2s

o17 = 18

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

i18 : T3s = allTriangulations(A, RegularOnly => false, ConnectedToRegular => false)

o18 = {triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4},
      -----------------------------------------------------------------------
      {0, 3, 5}, {1, 2, 3}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 2},
      -----------------------------------------------------------------------
      {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4},
      -----------------------------------------------------------------------
      {1, 2, 5}, {2, 4, 5}}, triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5},
      -----------------------------------------------------------------------
      {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 3},
      -----------------------------------------------------------------------
      {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4}, {2, 3, 5}, {2, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 3, 4}, {3, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3},
      -----------------------------------------------------------------------
      {1, 2, 4}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 1, 4},
      -----------------------------------------------------------------------
      {0, 1, 5}, {1, 2, 4}, {1, 2, 5}, {2, 4, 5}}, triangulation {{0, 1, 4},
      -----------------------------------------------------------------------
      {0, 1, 5}, {1, 3, 4}, {1, 3, 5}, {3, 4, 5}}, triangulation {{0, 1, 4},
      -----------------------------------------------------------------------
      {0, 1, 5}, {1, 4, 5}}, triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 4}, {3, 4, 5}}, triangulation {{0, 2, 3}, {0, 2, 4}, {0, 3, 5},
      -----------------------------------------------------------------------
      {2, 3, 5}, {2, 4, 5}}, triangulation {{0, 2, 4}, {0, 2, 5}, {2, 4, 5}},
      -----------------------------------------------------------------------
      triangulation {{0, 3, 4}, {0, 3, 5}, {3, 4, 5}}, triangulation {{0, 4,
      -----------------------------------------------------------------------
      5}}}

o18 : List
i19 : #T3s

o19 = 18

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

i20 : netList Ts

      +-------------------------------------------------------------------------------------------+
o20 = |triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5}}|
      +-------------------------------------------------------------------------------------------+
      |triangulation {{0, 1, 2}, {0, 1, 3}, {0, 2, 4}, {0, 3, 5}, {1, 2, 3}, {2, 3, 5}, {2, 4, 5}}|
      +-------------------------------------------------------------------------------------------+
      |triangulation {{0, 1, 3}, {0, 1, 4}, {0, 3, 5}, {1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {3, 4, 5}}|
      +-------------------------------------------------------------------------------------------+
      |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 4}, {3, 4, 5}}|
      +-------------------------------------------------------------------------------------------+
      |triangulation {{0, 1, 2}, {0, 1, 5}, {0, 2, 4}, {1, 2, 3}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}|
      +-------------------------------------------------------------------------------------------+
      |triangulation {{0, 1, 4}, {0, 1, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}}|
      +-------------------------------------------------------------------------------------------+
i21 : for tri in Ts list isWellDefined tri

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

o21 : List
i22 : for tri in Ts list isRegularTriangulation tri

o22 = {true, true, true, true, true, true}

o22 : List
i23 : for tri in Ts list regularTriangulationWeights tri

        97  47  1             87  41    1             157  15  1           
o23 = {{--, --, -, 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

o23 : List

See also

Ways to use this method: