Macaulay2 » Documentation
Packages » Triangulations :: Triangulations
next | previous | forward | backward | up | index | toc

Triangulations -- generating and manipulating triangulations of point or vector configurations

Description

Warning! This package is experimental, and the interface may still be cleaned up and changed (including defaults of optional arguments). Use only if that bothers you not!

Data of a triangulation

Creating triangulations

Properties of triangulations

Exploring the set of triangulations

Volumes and GKZ vectors

Delaunay subdivisions

Chirotopes

  • Chirotope -- the chirotope (oriented matroid) of a point or vector configuration
  • chirotope(Matrix) -- compute the chirotope of a point or vector configuration
  • naiveChirotope(Matrix) -- compute the chirotope of a configuration via determinants in Macaulay2

This package is designed to help compute and explore the set of all (or many) triangulations of a point set or a vector configuration.

We give a sample use of this package.

i1 : LP = {{-1, 0, -1, 1}, {-1, 0, 1, 0}, {-1, 0, 2, -1}, {-1, 1, -1, 0}, {1, 0, -1, 0}, {1, 0, 1, 0}, {2, -1, -1, 0}, {0, 0, 1, 0}, {1, 0, 0, 0}, {0,0,0,0}}

o1 = {{-1, 0, -1, 1}, {-1, 0, 1, 0}, {-1, 0, 2, -1}, {-1, 1, -1, 0}, {1, 0,
     ------------------------------------------------------------------------
     -1, 0}, {1, 0, 1, 0}, {2, -1, -1, 0}, {0, 0, 1, 0}, {1, 0, 0, 0}, {0, 0,
     ------------------------------------------------------------------------
     0, 0}}

o1 : List
 
i2 : A = transpose matrix LP

o2 = | -1 -1 -1 -1 1  1 2  0 1 0 |
     | 0  0  0  1  0  0 -1 0 0 0 |
     | -1 1  2  -1 -1 1 -1 1 0 0 |
     | 1  0  -1 0  0  0 0  0 0 0 |

              4       10
o2 : Matrix ZZ  <-- ZZ
 
i3 : elapsedTime Ts = allTriangulations(A, Fine => true);
 -- .0671719s elapsed
 
i4 : select(Ts, T -> isStar T)

o4 = {triangulation {{0, 1, 2, 3, 9}, {0, 1, 2, 6, 9}, {0, 1, 3, 7, 9}, {0,
     ------------------------------------------------------------------------
     1, 6, 7, 9}, {0, 2, 3, 6, 9}, {0, 3, 4, 6, 9}, {0, 3, 4, 8, 9}, {0, 3,
     ------------------------------------------------------------------------
     5, 7, 9}, {0, 3, 5, 8, 9}, {0, 4, 6, 8, 9}, {0, 5, 6, 7, 9}, {0, 5, 6,
     ------------------------------------------------------------------------
     8, 9}, {1, 2, 3, 7, 9}, {1, 2, 6, 7, 9}, {2, 3, 4, 6, 9}, {2, 3, 4, 8,
     ------------------------------------------------------------------------
     9}, {2, 3, 5, 7, 9}, {2, 3, 5, 8, 9}, {2, 4, 6, 8, 9}, {2, 5, 6, 7, 9},
     ------------------------------------------------------------------------
     {2, 5, 6, 8, 9}}}

o4 : List
 
i5 : #oo == 1

o5 = true
 
i6 : #Ts == 51

o6 = true
 
i7 : T = regularFineTriangulation A

o7 = triangulation {{0, 1, 2, 3, 9}, {0, 1, 2, 6, 9}, {0, 1, 3, 7, 9}, {0, 1, 6, 7, 9}, {0, 2, 3, 4, 6}, {0, 2, 3, 4, 9}, {0, 2, 4, 6, 9}, {0, 3, 4, 7, 8}, {0, 3, 4, 7, 9}, {0, 3, 5, 7, 8}, {0, 4, 6, 7, 8}, {0, 4, 6, 7, 9}, {0, 5, 6, 7, 8}, {1, 2, 3, 7, 9}, {1, 2, 6, 7, 9}, {2, 3, 4, 7, 8}, {2, 3, 4, 7, 9}, {2, 3, 5, 7, 8}, {2, 4, 6, 7, 8}, {2, 4, 6, 7, 9}, {2, 5, 6, 7, 8}}

o7 : Triangulation
 
i8 : elapsedTime Ts2 = generateTriangulations T;
 -- 1.37443s elapsed
 
i9 : #Ts2 == #Ts

o9 = true

See also

Author

Version

This documentation describes version 0.6 of Triangulations, released 5 June 2026.

Citation

If you have used this package in your research, please cite it as follows:

@misc{TriangulationsSource,
  title = {{Triangulations: triangulations of polyhedra and point sets. Version~0.6}},
  author = {Mike Stillman},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/stable/M2/Macaulay2/packages}}
}

Exports

  • Types
    • Chirotope -- the chirotope (oriented matroid) of a point or vector configuration
    • Triangulation -- a triangulation of a point or vector configuration
  • Functions and commands
    • allTriangulations -- see allTriangulations(Matrix) -- use topcom to generate all triangulations of a point or vector configuration
    • bistellarFlip -- perform a bistellar flip on a triangulation
    • chirotope -- compute the chirotope of a point or vector configuration
    • degreeMatrix -- charge matrix Q whose rows generate ker A
    • delaunaySubdivision -- the Delaunay subdivision of a point set
    • delaunayWeights -- squared-norm weights inducing the Delaunay subdivision of a point set
    • fineStarTriangulation -- refine a triangulation to a fine star triangulation by coning over a center
    • flipCandidates -- candidate affine circuits for bistellar flips of a triangulation
    • flipGraph -- bistellar-flip graph of a point or vector configuration
    • flips -- legal bistellar flips of a triangulation, computed via topcom
    • generateTriangulations -- generate all triangulations with certain properties
    • gkzVector (missing documentation)
    • isFine -- test whether a triangulation uses every point in the configuration
    • isRegularTriangulation -- determine if a given triangulation is a regular triangulation
    • isStar -- test whether a triangulation is a star with respect to its last point
    • makeFine -- walk to a fine triangulation by support-increasing bistellar flips
    • naiveChirotope -- compute the chirotope of a configuration via determinants in Macaulay2
    • neighbors -- triangulations adjacent to a given one in the bistellar-flip graph
    • regularFineFanTriangulation -- a regular fine star fan triangulation of a vector configuration
    • regularFineStarTriangulation -- a regular fine star triangulation of a polytope's boundary
    • regularFineTriangulation -- a regular fine triangulation of a point or vector configuration
    • regularTriangulationWeights -- height vector inducing a regular triangulation, if one exists
    • secondaryCone -- secondary cone of a triangulation, in charge-lattice coordinates
    • someTriangulation -- a triangulation of a point or vector configuration, not necessarily fine or regular
    • triangulation -- make a Triangulation object
    • vectors -- the column vectors of the configuration underlying a triangulation
    • volumeVector -- the GKZ vector (per-vertex/per-ray volume sum) of a triangulation
    • wallCircuits -- distinct codim-2 wall circuits of a triangulation, with sign convention
  • Methods
    • allTriangulations(Matrix) -- use topcom to generate all triangulations of a point or vector configuration
    • bistellarFlip(List,List) -- see bistellarFlip -- perform a bistellar flip on a triangulation
    • bistellarFlip(Triangulation,List) -- see bistellarFlip -- perform a bistellar flip on a triangulation
    • chirotope(Matrix) -- see chirotope -- compute the chirotope of a point or vector configuration
    • chirotope(String) -- see chirotope -- compute the chirotope of a point or vector configuration
    • Chirotope == Chirotope (missing documentation)
    • degreeMatrix(Matrix) -- see degreeMatrix -- charge matrix Q whose rows generate ker A
    • degreeMatrix(Triangulation) -- see degreeMatrix -- charge matrix Q whose rows generate ker A
    • delaunaySubdivision(Matrix) -- see delaunaySubdivision -- the Delaunay subdivision of a point set
    • delaunayWeights(Matrix) -- see delaunayWeights -- squared-norm weights inducing the Delaunay subdivision of a point set
    • fineStarTriangulation(Matrix,List) -- see fineStarTriangulation -- refine a triangulation to a fine star triangulation by coning over a center
    • flipCandidates(Matrix,List) -- see flipCandidates -- candidate affine circuits for bistellar flips of a triangulation
    • flipCandidates(Triangulation) -- see flipCandidates -- candidate affine circuits for bistellar flips of a triangulation
    • flipGraph(Matrix) -- see flipGraph -- bistellar-flip graph of a point or vector configuration
    • flipGraph(Matrix,List) -- see flipGraph -- bistellar-flip graph of a point or vector configuration
    • flipGraph(Triangulation) -- see flipGraph -- bistellar-flip graph of a point or vector configuration
    • flips(Triangulation) -- see flips -- legal bistellar flips of a triangulation, computed via topcom
    • generateTriangulations(Matrix) -- see generateTriangulations -- generate all triangulations with certain properties
    • generateTriangulations(Matrix,List) (missing documentation)
    • generateTriangulations(Triangulation) (missing documentation)
    • isFine(Matrix,List) -- see isFine -- test whether a triangulation uses every point in the configuration
    • isFine(Triangulation) -- see isFine -- test whether a triangulation uses every point in the configuration
    • isRegularTriangulation(Matrix,List) -- see isRegularTriangulation -- determine if a given triangulation is a regular triangulation
    • isRegularTriangulation(Triangulation) -- see isRegularTriangulation -- determine if a given triangulation is a regular triangulation
    • isStar(Matrix,List) -- see isStar -- test whether a triangulation is a star with respect to its last point
    • isStar(Triangulation) -- see isStar -- test whether a triangulation is a star with respect to its last point
    • isWellDefined(Triangulation) -- test whether the simplices of a triangulation form a valid triangulation
    • makeFine(Triangulation) -- see makeFine -- walk to a fine triangulation by support-increasing bistellar flips
    • matrix(Triangulation) -- the matrix whose columns are the points of a triangulation
    • max(Triangulation) -- the maximal simplices of a triangulation
    • naiveChirotope(Matrix) -- see naiveChirotope -- compute the chirotope of a configuration via determinants in Macaulay2
    • neighbors(Triangulation) -- see neighbors -- triangulations adjacent to a given one in the bistellar-flip graph
    • net(Triangulation) (missing documentation)
    • regularFineFanTriangulation(Matrix) -- see regularFineFanTriangulation -- a regular fine star fan triangulation of a vector configuration
    • regularFineStarTriangulation(Matrix) -- see regularFineStarTriangulation -- a regular fine star triangulation of a polytope's boundary
    • regularFineTriangulation(Matrix) -- see regularFineTriangulation -- a regular fine triangulation of a point or vector configuration
    • regularFineTriangulation(Triangulation) -- see regularFineTriangulation -- a regular fine triangulation of a point or vector configuration
    • regularTriangulationWeights(Matrix,List) -- see regularTriangulationWeights -- height vector inducing a regular triangulation, if one exists
    • regularTriangulationWeights(Triangulation) -- see regularTriangulationWeights -- height vector inducing a regular triangulation, if one exists
    • secondaryCone(Matrix,List) -- see secondaryCone -- secondary cone of a triangulation, in charge-lattice coordinates
    • secondaryCone(Triangulation) -- see secondaryCone -- secondary cone of a triangulation, in charge-lattice coordinates
    • someTriangulation(Matrix) -- see someTriangulation -- a triangulation of a point or vector configuration, not necessarily fine or regular
    • toExternalString(Triangulation) (missing documentation)
    • topcomIsRegularTriangulation(Triangulation) (missing documentation)
    • topcomRegularTriangulationWeights(Triangulation) (missing documentation)
    • toString(Chirotope) (missing documentation)
    • toString(Triangulation) (missing documentation)
    • triangulation(List,List) -- see triangulation -- make a Triangulation object
    • triangulation(Matrix,List) -- see triangulation -- make a Triangulation object
    • Triangulation == Triangulation (missing documentation)
    • vectors(Triangulation) -- see vectors -- the column vectors of the configuration underlying a triangulation
    • volumeVector(Matrix,List) -- see volumeVector -- the GKZ vector (per-vertex/per-ray volume sum) of a triangulation
    • volumeVector(Triangulation) -- see volumeVector -- the GKZ vector (per-vertex/per-ray volume sum) of a triangulation
    • wallCircuits(Matrix,List) -- see wallCircuits -- distinct codim-2 wall circuits of a triangulation, with sign convention
    • wallCircuits(Triangulation) -- see wallCircuits -- distinct codim-2 wall circuits of a triangulation, with sign convention
  • Symbols
    • ConeIndex -- optional argument: index of the cone center for star triangulations
    • Edges (missing documentation)
    • DegreeMatrix -- see secondaryCone -- secondary cone of a triangulation, in charge-lattice coordinates

For the programmer

The object Triangulations is a package, defined in Triangulations.m2.

The source of this document is in Triangulations.m2:1094:0.