Triangulations of a point configuration

A point configuration is a finite set of points in Euclidean space or, more generally, in projective space. A triangulation is a simplicial decomposition of the convex hull of a given point configuration such that all vertices of the simplices end up lying on points of the configuration. That is, there are no new vertices apart from the initial points.

Note that points that are not vertices of the convex hull need not be used in the triangulation. A triangulation that does make use of all points of the configuration is called fine, and you can restrict yourself to such triangulations if you want. See PointConfiguration and restrict_to_fine_triangulations() for more details.

Finding a single triangulation and listing all connected triangulations is implemented natively in this package. However, for more advanced options [TOPCOM] needs to be installed. It is available as an optional package for Sage, and you can install it with the shell command

sage -i topcom

Note

TOPCOM and the internal algorithms tend to enumerate triangulations in a different order. This is why we always explicitly specify the engine as engine='topcom' or engine='internal' in the doctests. In your own applications, you do not need to specify the engine. By default, TOPCOM is used if it is available and the internal algorithms are used otherwise.

EXAMPLES:

First, we select the internal implementation for enumerating triangulations:

sage: PointConfiguration.set_engine('internal')   # to make doctests independent of TOPCOM

A 2-dimensional point configuration:

sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p
A point configuration in affine 2-space over Integer Ring consisting
of 5 points. The triangulations of this point configuration are
assumed to be connected, not necessarily fine, not necessarily regular.
../../../_images/point_configuration-1.png

A triangulation of it:

sage: t = p.triangulate()  # a single triangulation
sage: t
(<1,3,4>, <2,3,4>)
sage: len(t)
2
sage: t[0]
(1, 3, 4)
sage: t[1]
(2, 3, 4)
sage: list(t)
[(1, 3, 4), (2, 3, 4)]
sage: t.plot(axes=False)
Graphics object consisting of 12 graphics primitives
../../../_images/point_configuration-2.png

List triangulations of it:

sage: list( p.triangulations() )
[(<1,3,4>, <2,3,4>),
 (<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>),
 (<1,2,3>, <1,2,4>),
 (<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)]
sage: p_fine = p.restrict_to_fine_triangulations()
sage: p_fine
A point configuration in affine 2-space over Integer Ring consisting
of 5 points. The triangulations of this point configuration are
assumed to be connected, fine, not necessarily regular.
sage: list( p_fine.triangulations() )
[(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>),
 (<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)]

A 3-dimensional point configuration:

sage: p = [[0,-1,-1],[0,0,1],[0,1,0], [1,-1,-1],[1,0,1],[1,1,0]]
sage: points = PointConfiguration(p)
sage: triang = points.triangulate()
sage: triang.plot(axes=False)
Graphics3d Object
../../../_images/point_configuration-3.png

The standard example of a non-regular triangulation (requires TOPCOM):

sage: PointConfiguration.set_engine('topcom')   # optional - topcom
sage: p = PointConfiguration([[-1,-5/9],[0,10/9],[1,-5/9],[-2,-10/9],[0,20/9],[2,-10/9]])
sage: regular = p.restrict_to_regular_triangulations(True).triangulations_list()      # optional - topcom
sage: nonregular = p.restrict_to_regular_triangulations(False).triangulations_list()  # optional - topcom
sage: len(regular)     # optional - topcom
16
sage: len(nonregular)  # optional - topcom
2
sage: nonregular[0].plot(aspect_ratio=1, axes=False)   # optional - topcom
Graphics object consisting of 25 graphics primitives
sage: PointConfiguration.set_engine('internal')   # to make doctests independent of TOPCOM

Note that the points need not be in general position. That is, the points may lie in a hyperplane and the linear dependencies will be removed before passing the data to TOPCOM which cannot handle it:

sage: points = [[0,0,0,1],[0,3,0,1],[3,0,0,1],[0,0,1,1],[0,3,1,1],[3,0,1,1],[1,1,2,1]]
sage: points = [ p+[1,2,3] for p in points ]
sage: pc = PointConfiguration(points)
sage: pc.ambient_dim()
7
sage: pc.dim()
3
sage: pc.triangulate()
(<0,1,2,6>, <0,1,3,6>, <0,2,3,6>, <1,2,4,6>, <1,3,4,6>, <2,3,5,6>, <2,4,5,6>)
sage: _ in pc.triangulations()
True
sage: len( pc.triangulations_list() )
26

AUTHORS:

  • Volker Braun: initial version, 2010
  • Josh Whitney: added functionality for computing volumes and secondary polytopes of PointConfigurations
  • Marshall Hampton: improved documentation and doctest coverage
  • Volker Braun: rewrite using Parent/Element and catgories. Added a Point class. More doctests. Less zombies.
  • Volker Braun: Cythonized parts of it, added a C++ implementation of the bistellar flip algorithm to enumerate all connected triangulations.
  • Volker Braun 2011: switched the triangulate() method to the placing triangulation (faster).
sage.geometry.triangulation.point_configuration.PointConfiguration

A collection of points in Euclidean (or projective) space.

This is the parent class for the triangulations of the point configuration. There are a few options to specifically select what kind of triangulations are admissible.

INPUT:

The constructor accepts the following arguments:

  • points – the points. Technically, any iterable of iterables will do. In particular, a PointConfiguration can be passed.

  • projective – boolean (default: False). Whether the point coordinates should be interpreted as projective (True) or affine (False) coordinates. If necessary, points are projectivized by setting the last homogeneous coordinate to one and/or affine patches are chosen internally.

  • connected – boolean (default: True). Whether the triangulations should be connected to the regular triangulations via bistellar flips. These are much easier to compute than all triangulations.

  • fine – boolean (default: False). Whether the triangulations must be fine, that is, make use of all points of the configuration.

  • regular – boolean or None (default: None). Whether the triangulations must be regular. A regular triangulation is one that is induced by a piecewise-linear convex support function. In other words, the shadows of the faces of a polyhedron in one higher dimension.

    • True: Only regular triangulations.
    • False: Only non-regular triangulations.
    • None (default): Both kinds of triangulation.
  • star – either None or a point. Whether the triangulations must be star. A triangulation is star if all maximal simplices contain a common point. The central point can be specified by its index (an integer) in the given points or by its coordinates (anything iterable.)

EXAMPLES:

sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p
A point configuration in affine 2-space over Integer Ring
consisting of 5 points. The triangulations of this point
configuration are assumed to be connected, not necessarily fine,
not necessarily regular.
sage: p.triangulate()  # a single triangulation
(<1,3,4>, <2,3,4>)