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. You can find an experimental spkg at http://trac.sagemath.org/sage_trac/ticket/8169
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 QQ^2 consisting of 5 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
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)
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 QQ^2 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)
The standard example of a non-regular triangulation:
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
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,3>, <1,2,3,4>, <2,3,4,5>, <3,4,5,6>)
sage: len( pc.triangulations_list() )
26
REFERENCES:
[TOPCOM] J. Rambau, TOPCOM <http://www.rambau.wm.uni-bayreuth.de/TOPCOM/>.
[GKZ] (1, 2, 3) Gel’fand, I. M.; Kapranov, M. M.; and Zelevinsky, A. V. “Discriminants, Resultants and Multidimensional Determinants” Birkhauser 1994.
[PUNTOS] Jesus A. De Loera http://www.math.ucdavis.edu/~deloera/RECENT_WORK/puntos2000
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.
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.geometry.triangulation.base.PointConfiguration_base
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 QQ^2 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>)
alias of Triangulation
Synonymous for triangulate().
TESTS:
sage: p = PointConfiguration([[0, 1], [0, 0], [1, 0], [1,1]])
sage: p.an_element()
(<0,1,3>, <1,2,3>)
Return the bistellar flips.
OUTPUT:
The bistellar flips as a tuple. Each flip is a pair
where
and
are partial triangulations
of the point configuration.
EXAMPLES:
sage: pc = PointConfiguration([(0,0),(1,0),(0,1),(1,1)])
sage: pc.bistellar_flips()
(((<0,1,3>, <0,2,3>), (<0,1,2>, <1,2,3>)),)
sage: Tpos, Tneg = pc.bistellar_flips()[0]
sage: Tpos.plot(axes=False)
sage: Tneg.plot(axes=False)
The 3d analog:
sage: pc = PointConfiguration([(0,0,0),(0,2,0),(0,0,2),(-1,0,0),(1,1,1)])
sage: pc.bistellar_flips()
(((<0,1,2,3>, <0,1,2,4>), (<0,1,3,4>, <0,2,3,4>, <1,2,3,4>)),)
A 2d flip on the base of the pyramid over a square:
sage: pc = PointConfiguration([(0,0,0),(0,2,0),(0,0,2),(0,2,2),(1,1,1)])
sage: pc.bistellar_flips()
(((<0,1,3>, <0,2,3>), (<0,1,2>, <1,2,3>)),)
sage: Tpos, Tneg = pc.bistellar_flips()[0]
sage: Tpos.plot(axes=False)
Return the circuits of the point configuration.
Roughly, a circuit is a minimal linearly dependent subset of the points. That is, a circuit is a partition
such that there is an (unique up to an overall normalization) affine relation
with all positive (or all negative) coefficients, where
are the projective coordinates
of the
-th point.
OUTPUT:
The list of (unsigned) circuits as triples . The swapped circuit
is not returned
separately.
EXAMPLES:
sage: p = PointConfiguration([(0,0),(+1,0),(-1,0),(0,+1),(0,-1)])
sage: p.circuits()
(((0,), (1, 2), (3, 4)), ((0,), (3, 4), (1, 2)), ((1, 2), (0,), (3, 4)))
TESTS:
sage: U=matrix([
... [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0],
... [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0],
... [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1],
... [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1],
... [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0]
... ])
sage: p = PointConfiguration(U.columns())
sage: len( p.circuits() ) # long time
218
A generator for the supports of the circuits of the point configuration.
See circuits() for details.
OUTPUT:
A generator for the supports (returned as a
Python tuple) for all circuits of the point configuration.
EXAMPLES:
sage: p = PointConfiguration([(0,0),(+1,0),(-1,0),(0,+1),(0,-1)])
sage: list( p.circuits_support() )
[(0, 3, 4), (0, 1, 2), (1, 2, 3, 4)]
Return the convex hull of the point configuration.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p.convex_hull()
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices.
Return a new point configuration with the given points removed.
INPUT:
OUTPUT:
A new PointConfiguration with the given points removed.
EXAMPLES:
sage: p = PointConfiguration([[-1,0], [0,0], [1,-1], [1,0], [1,1]]);
sage: list(p)
[P(-1, 0), P(0, 0), P(1, -1), P(1, 0), P(1, 1)]
sage: q = p.exclude_points([3])
sage: list(q)
[P(-1, 0), P(0, 0), P(1, -1), P(1, 1)]
sage: p.exclude_points( p.face_interior(codim=1) ).points()
(P(-1, 0), P(0, 0), P(1, -1), P(1, 1))
Return the smallest such that point is
contained in the interior of a codimension-
face.
EXAMPLES:
sage: triangle = PointConfiguration([[0,0], [1,-1], [1,0], [1,1]]);
sage: triangle.point(2)
P(1, 0)
sage: triangle.face_codimension(2)
1
sage: triangle.face_codimension( [1,0] )
1
This also works for degenerate cases like the tip of the pyramid over a square (which saturates four inequalities):
sage: pyramid = PointConfiguration([[1,0,0],[0,1,1],[0,1,-1],[0,-1,-1],[0,-1,1]])
sage: pyramid.face_codimension(0)
3
Return points by the codimension of the containing face in the convex hull.
EXAMPLES:
sage: triangle = PointConfiguration([[-1,0], [0,0], [1,-1], [1,0], [1,1]]);
sage: triangle.face_interior()
((1,), (3,), (0, 2, 4))
sage: triangle.face_interior(dim=0) # the vertices of the convex hull
(0, 2, 4)
sage: triangle.face_interior(codim=1) # interior of facets
(3,)
Return the lexicographic triangulation.
The algorithm was taken from [PUNTOS].
EXAMPLES:
sage: p = PointConfiguration([(0,0),(+1,0),(-1,0),(0,+1),(0,-1)])
sage: p.lexicographic_triangulation()
(<1,3,4>, <2,3,4>)
TESTS:
sage: U=matrix([
... [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0],
... [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0],
... [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1],
... [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1],
... [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0]
... ])
sage: pc = PointConfiguration(U.columns())
sage: pc.lexicographic_triangulation()
(<1,3,4,7,10,13>, <1,3,4,8,10,13>, <1,3,6,7,10,13>, <1,3,6,8,10,13>,
<1,4,6,7,10,13>, <1,4,6,8,10,13>, <2,3,4,6,7,12>, <2,3,4,7,12,13>,
<2,3,6,7,12,13>, <2,4,6,7,12,13>, <3,4,5,6,9,12>, <3,4,5,8,9,12>,
<3,4,6,7,11,12>, <3,4,6,9,11,12>, <3,4,7,10,11,13>, <3,4,7,11,12,13>,
<3,4,8,9,10,12>, <3,4,8,10,12,13>, <3,4,9,10,11,12>, <3,4,10,11,12,13>,
<3,5,6,8,9,12>, <3,6,7,10,11,13>, <3,6,7,11,12,13>, <3,6,8,9,10,12>,
<3,6,8,10,12,13>, <3,6,9,10,11,12>, <3,6,10,11,12,13>, <4,5,6,8,9,12>,
<4,6,7,10,11,13>, <4,6,7,11,12,13>, <4,6,8,9,10,12>, <4,6,8,10,12,13>,
<4,6,9,10,11,12>, <4,6,10,11,12,13>)
sage: len(_)
34
Returns the positive part of circuits with fixed negative part.
A circuit is a pair , each consisting of a subset
(actually, an ordered tuple) of point indices.
INPUT:
OUTPUT:
A tuple of all circuits with .
EXAMPLE:
sage: p = PointConfiguration([(1,0,0),(0,1,0),(0,0,1),(-2,0,-1),(-2,-1,0),(-3,-1,-1),(1,1,1),(-1,0,0),(0,0,0)])
sage: p.positive_circuits(8)
((0, 7), (0, 1, 4), (0, 2, 3), (0, 5, 6), (0, 1, 2, 5), (0, 3, 4, 6))
sage: p.positive_circuits(0,5,6)
((8,),)
Restrict to connected triangulations.
NOTE:
Finding non-connected triangulations requires the optional TOPCOM package.
INPUT:
OUTPUT:
A new PointConfiguration with the same points, but whose triangulations will all be in the connected component. See PointConfiguration for details.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p
A point configuration in QQ^2 consisting of 5 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
sage: len(p.triangulations_list())
4
sage: p_all = p.restrict_to_connected_triangulations(connected=False) # optional - TOPCOM
sage: len(p_all.triangulations_list()) # optional - TOPCOM
4
sage: p == p_all.restrict_to_connected_triangulations(connected=True) # optional - TOPCOM
True
Restrict to fine triangulations.
INPUT:
OUTPUT:
A new PointConfiguration with the same points, but whose triangulations will all be fine. See PointConfiguration for details.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p
A point configuration in QQ^2 consisting of 5 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
sage: len(p.triangulations_list())
4
sage: p_fine = p.restrict_to_fine_triangulations()
sage: len(p.triangulations_list())
4
sage: p == p_fine.restrict_to_fine_triangulations(fine=False)
True
Restrict to regular triangulations.
NOTE:
Regularity testing requires the optional TOPCOM package.
INPUT:
OUTPUT:
A new PointConfiguration with the same points, but whose triangulations will all be regular as specified. See PointConfiguration for details.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p
A point configuration in QQ^2 consisting of 5 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
sage: len(p.triangulations_list())
4
sage: p_regular = p.restrict_to_regular_triangulations() # optional - TOPCOM
sage: len(p_regular.triangulations_list()) # optional - TOPCOM
4
sage: p == p_regular.restrict_to_regular_triangulations(regular=None) # optional - TOPCOM
True
Restrict to star triangulations with the given point as the center.
INPUT:
OUTPUT:
A new PointConfiguration with the same points, but whose triangulations will all be star. See PointConfiguration for details.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: len(list( p.triangulations() ))
4
sage: p_star = p.restrict_to_star_triangulations(0)
sage: p_star is p.restrict_to_star_triangulations((0,0))
True
sage: p_star.triangulations_list()
[(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>)]
sage: p_newstar = p_star.restrict_to_star_triangulations(1) # pick different origin
sage: p_newstar.triangulations_list()
[(<1,2,3>, <1,2,4>)]
sage: p == p_star.restrict_to_star_triangulations(star=None)
True
Return the restricted automorphism group.
First, let the linear automorphism group be the subgroup of
the Euclidean group
preserving the
-dimensional point configuration. The
Euclidean group acts in the usual way
on the ambient space.
The restricted automorphism group is the subgroup of the linear automorphism group generated by permutations of points. See [BSS] for more details and a description of the algorithm.
OUTPUT:
A PermutationGroup that is isomorphic to the restricted automorphism group is returned.
Note that in Sage, permutation groups always act on positive
integers while lists etc. are indexed by nonnegative
integers. The indexing of the permutation group is chosen to
be shifted by +1. That is, the transposition (i,j) in
the permutation group corresponds to exchange of
and
.
EXAMPLES:
sage: pyramid = PointConfiguration([[1,0,0],[0,1,1],[0,1,-1],[0,-1,-1],[0,-1,1]])
sage: pyramid.restricted_automorphism_group()
Permutation Group with generators [(3,5), (2,3)(4,5), (2,4)]
sage: DihedralGroup(4).is_isomorphic(_)
True
The square with an off-center point in the middle. Note thath
the middle point breaks the restricted automorphism group
of the convex hull:
sage: square = PointConfiguration([(3/4,3/4),(1,1),(1,-1),(-1,-1),(-1,1)])
sage: square.restricted_automorphism_group()
Permutation Group with generators [(3,5)]
sage: DihedralGroup(1).is_isomorphic(_)
True
Calculate the secondary polytope of the point configuration.
For a definition of the secondary polytope, see [GKZ] page 220 Definition 1.6.
Note that if you restricted the admissible triangulations of the point configuration then the output will be the corresponding face of the whole secondary polytope.
OUTPUT:
The secondary polytope of the point configuration as an instance of sage.geometry.polyhedra.Polyhedron.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[1,0],[2,1],[1,2],[0,1]])
sage: poly = p.secondary_polytope()
sage: matrix(poly.vertices()).transpose()
[1 3 1 5 3]
[3 1 5 1 4]
[4 5 2 4 2]
[2 2 4 4 5]
[5 4 3 1 1]
sage: poly.Vrepresentation()
[A vertex at (1, 3, 4, 2, 5),
A vertex at (3, 1, 5, 2, 4),
A vertex at (1, 5, 2, 4, 3),
A vertex at (5, 1, 4, 4, 1),
A vertex at (3, 4, 2, 5, 1)]
sage: poly.Hrepresentation()
[An equation (1/2, 1, 1, 0, 0) x - 15/2 == 0,
An equation (-1, -1, 0, 1, 0) x + 2 == 0,
An equation (3/2, 1, 0, 0, 1) x - 19/2 == 0,
An inequality (-1, -2, 0, 0, 0) x + 11 >= 0,
An inequality (1, 0, 0, 0, 0) x - 1 >= 0,
An inequality (1, 1, 0, 0, 0) x - 4 >= 0,
An inequality (0, 1, 0, 0, 0) x - 1 >= 0,
An inequality (-3/2, -1, 0, 0, 0) x + 17/2 >= 0]
Set the engine used to compute triangulations.
INPUT:
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p.set_engine('internal') # to make doctests independent of TOPCOM
sage: p.triangulate()
(<1,3,4>, <2,3,4>)
sage: p.set_engine('TOPCOM') # optional - TOPCOM
sage: p.triangulate() # optional - TOPCOM
(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)
sage: p.set_engine('internal') # optional - TOPCOM
Return one (in no particular order) triangulation.
INPUT:
OUTPUT:
A Triangulation satisfying all restrictions imposed. Raises a ValueError if no such triangulation exists.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: p.triangulate()
(<1,3,4>, <2,3,4>)
sage: list( p.triangulate() )
[(1, 3, 4), (2, 3, 4)]
Using TOPCOM yields a different, but equally good, triangulation:
sage: p.set_engine('TOPCOM') # optional - TOPCOM
sage: p.triangulate() # optional - TOPCOM
(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)
sage: list( p.triangulate() ) # optional - TOPCOM
[(0, 1, 2), (0, 1, 4), (0, 2, 4), (1, 2, 3)]
sage: p.set_engine('internal') # optional - TOPCOM
Returns all triangulations.
OUTPUT:
A generator for the triangulations satisfying all the restrictions imposed. Each triangulation is returned as a Triangulation object.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: iter = p.triangulations()
sage: iter.next()
(<1,3,4>, <2,3,4>)
sage: iter.next()
(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>)
sage: iter.next()
(<1,2,3>, <1,2,4>)
sage: iter.next()
(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)
sage: p.triangulations_list()
[(<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.triangulations_list()
[(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>),
(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)]
Note that we explicitly asked the internal algorithm to
compute the triangulations. Using TOPCOM, we obtain the same
triangulations but in a different order::
sage: p.set_engine('TOPCOM') # optional - TOPCOM
sage: iter = p.triangulations() # optional - TOPCOM
sage: iter.next() # optional - TOPCOM
(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>)
sage: iter.next() # optional - TOPCOM
(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>)
sage: iter.next() # optional - TOPCOM
(<1,2,3>, <1,2,4>)
sage: iter.next() # optional - TOPCOM
(<1,3,4>, <2,3,4>)
sage: p.triangulations_list() # optional - TOPCOM
[(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>),
(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>),
(<1,2,3>, <1,2,4>),
(<1,3,4>, <2,3,4>)]
sage: p_fine = p.restrict_to_fine_triangulations() # optional - TOPCOM
sage: p_fine.set_engine('TOPCOM') # optional - TOPCOM
sage: p_fine.triangulations_list() # optional - TOPCOM
[(<0,1,2>, <0,1,4>, <0,2,4>, <1,2,3>),
(<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>)]
sage: p.set_engine('internal') # optional - TOPCOM
Return all triangulations.
INPUT:
OUTPUT:
A list of triangulations (see Triangulation) satisfying all restrictions imposed previously.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1]])
sage: p.triangulations_list()
[(<0,1,2>, <1,2,3>), (<0,1,3>, <0,2,3>)]
sage: map(list, p.triangulations_list() )
[[(0, 1, 2), (1, 2, 3)], [(0, 1, 3), (0, 2, 3)]]
sage: p.set_engine('TOPCOM') # optional - TOPCOM
sage: p.triangulations_list() # optional - TOPCOM
[(<0,1,2>, <1,2,3>), (<0,1,3>, <0,2,3>)]
sage: p.set_engine('internal') # optional - TOPCOM
Find n! times the n-volume of a simplex of dimension n.
INPUT:
OUTPUT:
EXAMPLES:
The volume of the standard simplex should always be 1:
sage: p = PointConfiguration([[0,0],[1,0],[0,1],[1,1]])
sage: p.volume( [0,1,2] )
1
sage: simplex = p.triangulate()[0] # first simplex of triangulation
sage: p.volume(simplex)
1
The square can be triangulated into two minimal simplices, so in the “integral” normalization ts volume equals two:
sage: p.volume()
2
NOTES:
We need to have n!*(volume of the simplex) to ensure that the volume is an integer. Essentially, this normalizes things so that the volume of the standard n-simplex is 1. See [GKZ] page 182.
Bases: sage.structure.element.Element
A triangulation of a PointConfiguration.
Warning
You should never create Triangulation objects manually. See triangulate() and triangulations() to triangulate point configurations.
Return the enumerated simplices.
OUTPUT:
A tuple of integers that uniquely specifies the triangulation.
EXAMPLES:
sage: pc = PointConfiguration(matrix([
... [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0],
... [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0],
... [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1],
... [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1],
... [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0]
... ]).columns())
sage: triangulation = pc.lexicographic_triangulation()
sage: triangulation.enumerate_simplices()
(1678, 1688, 1769, 1779, 1895, 1905, 2112, 2143, 2234, 2360, 2555, 2580,
2610, 2626, 2650, 2652, 2654, 2661, 2663, 2667, 2685, 2755, 2757, 2759,
2766, 2768, 2772, 2811, 2881, 2883, 2885, 2892, 2894, 2898)
You can recreate the triangulation from this list by passing it to the constructor:
sage: from sage.geometry.triangulation.point_configuration import Triangulation
sage: Triangulation([1678, 1688, 1769, 1779, 1895, 1905, 2112, 2143,
... 2234, 2360, 2555, 2580, 2610, 2626, 2650, 2652, 2654, 2661, 2663,
... 2667, 2685, 2755, 2757, 2759, 2766, 2768, 2772, 2811, 2881, 2883,
... 2885, 2892, 2894, 2898], pc)
(<1,3,4,7,10,13>, <1,3,4,8,10,13>, <1,3,6,7,10,13>, <1,3,6,8,10,13>,
<1,4,6,7,10,13>, <1,4,6,8,10,13>, <2,3,4,6,7,12>, <2,3,4,7,12,13>,
<2,3,6,7,12,13>, <2,4,6,7,12,13>, <3,4,5,6,9,12>, <3,4,5,8,9,12>,
<3,4,6,7,11,12>, <3,4,6,9,11,12>, <3,4,7,10,11,13>, <3,4,7,11,12,13>,
<3,4,8,9,10,12>, <3,4,8,10,12,13>, <3,4,9,10,11,12>, <3,4,10,11,12,13>,
<3,5,6,8,9,12>, <3,6,7,10,11,13>, <3,6,7,11,12,13>, <3,6,8,9,10,12>,
<3,6,8,10,12,13>, <3,6,9,10,11,12>, <3,6,10,11,12,13>, <4,5,6,8,9,12>,
<4,6,7,10,11,13>, <4,6,7,11,12,13>, <4,6,8,9,10,12>, <4,6,8,10,12,13>,
<4,6,9,10,11,12>, <4,6,10,11,12,13>)
Calculate the GKZ phi vector of the triangulation.
OUTPUT:
Vector – the phi vector of self.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[1,0],[2,1],[1,2],[0,1]])
sage: p.triangulate().gkz_phi()
(1, 3, 4, 2, 5)
NOTE:
For a definition of the phi vector, see [GKZ] page 220 equation 1.4.
Produce a graphical representation of the triangulation.
EXAMPLES:
sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: triangulation = p.triangulate()
sage: triangulation
(<1,3,4>, <2,3,4>)
sage: triangulation.plot(axes=False)
Returns the point configuration underlying the triangulation.
EXAMPLES:
sage: pconfig = PointConfiguration([[0,0],[0,1],[1,0]])
sage: pconfig
A point configuration in QQ^2 consisting of 3 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
sage: triangulation = pconfig.triangulate()
sage: triangulation
(<0,1,2>)
sage: triangulation.point_configuration()
A point configuration in QQ^2 consisting of 3 points. The
triangulations of this point configuration are assumed to
be connected, not necessarily fine, not necessarily regular.
sage: pconfig == triangulation.point_configuration()
True
Return a graphical representation of a 2-d triangulation.
INPUT:
OUTPUT:
A 2-d graphics object.
EXAMPLES:
sage: points = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
sage: triang = points.triangulate()
sage: triang.plot(axes=False) # indirect doctest
Return a graphical representation of a 3-d triangulation.
INPUT:
OUTPUT:
A 3-d graphics object.
EXAMPLES:
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) # indirect doctest