Bases: sage.structure.element.Element
Base class for Polyhedron objects
INPUT:
Only one of Vrep or Hrep can be different from None.
TESTS:
sage: p = Polyhedron()
sage: TestSuite(p).run()
Return an iterator over the objects of the H-representation (inequalities or equations).
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: p.Hrep_generator().next()
An inequality (0, 0, -1) x + 1 >= 0
Return the objects of the H-representaton. Each entry is either an inequality or a equation.
INPUT:
OUTPUT:
The optional argument is an index running from 0 to self.n_Hrepresentation()-1. If present, the H-representation object at the given index will be returned. Without an argument, returns the list of all H-representation objects.
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: p.Hrepresentation(0)
An inequality (0, 0, -1) x + 1 >= 0
sage: p.Hrepresentation(0) == p.Hrepresentation() [0]
True
Return the linear space containing the H-representation vectors.
OUTPUT:
A free module over the base ring of dimension ambient_dim() + 1.
EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.Hrepresentation_space()
Ambient free module of rank 5 over the principal ideal domain Integer Ring
Return the Minkowski difference.
Minkowski subtraction can equivalently be defined via Minkowski addition (see Minkowski_sum()) or as set-theoretic intersection via
where superscript-“c” means the complement in the ambient vector space. The Minkowski difference of convex sets is convex, and the difference of polyhedra is again a polyhedron. We only consider the case of polyhedra in the following. Note that it is not quite the inverse of addition. In fact:
INPUT:
OUTPUT:
The Minkowski difference of self and other. Also known as Minkowski subtraction of other from self.
EXAMPLES:
sage: X = polytopes.n_cube(3)
sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1), (0,1,0), (1,0,0)]) / 2
sage: (X+Y)-Y == X
True
sage: (X-Y)+Y < X
True
The polyhedra need not be full-dimensional:
sage: X2 = Polyhedron(vertices=[(-1,-1,0),(1,-1,0),(-1,1,0),(1,1,0)])
sage: Y2 = Polyhedron(vertices=[(0,0,0), (0,1,0), (1,0,0)]) / 2
sage: (X2+Y2)-Y2 == X2
True
sage: (X2-Y2)+Y2 < X2
True
Minus sign is really an alias for Minkowski_difference()
sage: four_cube = polytopes.n_cube(4)
sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]])
sage: four_cube - four_simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices
sage: four_cube.Minkowski_difference(four_simplex) == four_cube - four_simplex
True
Coercion of the base ring works:
sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ)
sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ) / 100
sage: poly_spam - poly_eggs
A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 5 vertices
TESTS:
sage: X = polytopes.n_cube(2)
sage: Y = Polyhedron(vertices=[(1,1)])
sage: (X-Y).Vrepresentation()
(A vertex at (0, -2), A vertex at (0, 0), A vertex at (-2, 0), A vertex at (-2, -2))
sage: Y = Polyhedron(vertices=[(1,1), (0,0)])
sage: (X-Y).Vrepresentation()
(A vertex at (0, -1), A vertex at (0, 0), A vertex at (-1, 0), A vertex at (-1, -1))
sage: X = X + Y # now Y is a Minkowski summand of X
sage: (X+Y)-Y == X
True
sage: (X-Y)+Y == X
True
Return the Minkowski sum.
Minkowski addition of two subsets of a vector space is defined as
See Minkowski_difference() for a partial inverse operation.
INPUT:
OUTPUT:
The Minkowski sum of self and other.
EXAMPLES:
sage: X = polytopes.n_cube(3)
sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1/2), (0,1/2,0), (1/2,0,0)])
sage: X+Y
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 13 vertices
sage: four_cube = polytopes.n_cube(4)
sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]])
sage: four_cube + four_simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 36 vertices
sage: four_cube.Minkowski_sum(four_simplex) == four_cube + four_simplex
True
sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ)
sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ)
sage: poly_spam + poly_spam + poly_eggs
A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 12 vertices
Returns an iterator over the objects of the V-representation (vertices, rays, and lines).
EXAMPLES:
sage: p = polytopes.cyclic_polytope(3,4)
sage: vg = p.Vrep_generator()
sage: vg.next()
A vertex at (0, 0, 0)
sage: vg.next()
A vertex at (1, 1, 1)
Return the objects of the V-representation. Each entry is either a vertex, a ray, or a line.
See sage.geometry.polyhedron.constructor for a definition of vertex/ray/line.
INPUT:
OUTPUT:
The optional argument is an index running from 0 to \(self.n_Vrepresentation()-1`\). If present, the V-representation object at the given index will be returned. Without an argument, returns the list of all V-representation objects.
EXAMPLES:
sage: p = polytopes.n_simplex(4)
sage: p.Vrepresentation(0)
A vertex at (-7071/10000, 1633/4000, 7217/25000, 22361/100000)
sage: p.Vrepresentation(0) == p.Vrepresentation() [0]
True
Return the ambient vector space.
OUTPUT:
A free module over the base ring of dimension ambient_dim().
EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.Vrepresentation_space()
Ambient free module of rank 4 over the principal ideal domain Integer Ring
sage: poly_test.ambient_space() is poly_test.Vrepresentation_space()
True
Return the binary matrix of vertex adjacencies.
EXAMPLES:
sage: polytopes.n_simplex(4).vertex_adjacency_matrix()
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
The rows and columns of the vertex adjacency matrix correspond to the Vrepresentation() objects: vertices, rays, and lines. The \((i,j)\) matrix entry equals \(1\) if the \(i\)-th and \(j\)-th V-representation object are adjacent.
Two vertices are adjacent if they are the endpoints of an edge, that is, a one-dimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two V-representation objects (see sage.geometry.polyhedron.constructor) to be adjacent if they together generate a one-face. There are three possible combinations:
For example, take the half-plane:
sage: half_plane = Polyhedron(ieqs=[(0,1,0)])
sage: half_plane.Hrepresentation()
(An inequality (1, 0) x + 0 >= 0,)
Its (non-unique) V-representation consists of a vertex, a ray, and a line. The only edge is spanned by the vertex and the line generator, so they are adjacent:
sage: half_plane.Vrepresentation()
(A line in the direction (0, 1), A ray in the direction (1, 0), A vertex at (0, 0))
sage: half_plane.vertex_adjacency_matrix()
[0 0 1]
[0 0 0]
[1 0 0]
In one dimension higher, that is for a half-space in 3 dimensions, there is no one-dimensional face. Hence nothing is adjacent:
sage: Polyhedron(ieqs=[(0,1,0,0)]).vertex_adjacency_matrix()
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
EXAMPLES:
In a bounded polygon, every vertex has precisely two adjacent ones:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)])
sage: for v in P.Vrep_generator():
... print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 1) A vertex at (0, 1)
(1, 0, 1, 0) A vertex at (1, 0)
(0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
... rays=[(0,1)])
sage: for v in P.Vrep_generator():
... print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 1) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 1, 0) A vertex at (1, 0)
(0, 0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
... rays=[(0,1), (1,1)])
sage: for v in P.Vrep_generator():
... print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 0) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 0, 1) A vertex at (1, 0)
(0, 0, 0, 0, 1) A ray in the direction (1, 1)
(0, 0, 1, 1, 0) A vertex at (3, 0)
Return the affine hull.
Each polyhedron is contained in some smallest affine subspace (possibly the entire ambient space). The affine hull is the same polyhedron but thought of as a full-dimensional polyhedron in this subspace.
OUTPUT:
A full-dimensional polyhedron.
EXAMPLES:
sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]); triangle
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: triangle.affine_hull()
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
sage: half3d = Polyhedron(vertices=[(3,2,1)], rays=[(1,0,0)])
sage: half3d.affine_hull().Vrepresentation()
(A ray in the direction (1), A vertex at (3))
TESTS:
sage: Polyhedron([(2,3,4)]).affine_hull()
A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex
Return the dimension of the ambient space.
EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.ambient_dim()
4
Return the ambient vector space.
OUTPUT:
A free module over the base ring of dimension ambient_dim().
EXAMPLES:
sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.Vrepresentation_space()
Ambient free module of rank 4 over the principal ideal domain Integer Ring
sage: poly_test.ambient_space() is poly_test.Vrepresentation_space()
True
Return a new polyhedron over a larger field.
INPUT:
OUTPUT:
The same polyhedron, but over a larger base ring.
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,0), (0,1)], rays=[(1,1)], base_ring=ZZ); P
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.base_extend(QQ)
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.base_extend(QQ) == P
True
Return the base ring.
OUTPUT:
Either QQ (exact arithmetic using gmp, default) or RDF (double precision floating-point arithmetic)
EXAMPLES:
sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]])
sage: triangle.base_ring() == ZZ
True
Return a polyhedron that is a bipyramid over the original.
EXAMPLES:
sage: octahedron = polytopes.cross_polytope(3)
sage: cross_poly_4d = octahedron.bipyramid()
sage: cross_poly_4d.n_vertices()
8
sage: q = [list(v) for v in cross_poly_4d.vertex_generator()]
sage: q
[[-1, 0, 0, 0],
[0, -1, 0, 0],
[0, 0, -1, 0],
[0, 0, 0, -1],
[0, 0, 0, 1],
[0, 0, 1, 0],
[0, 1, 0, 0],
[1, 0, 0, 0]]
Now check that bipyramids of cross-polytopes are cross-polytopes:
sage: q2 = [list(v) for v in polytopes.cross_polytope(4).vertex_generator()]
sage: [v in q2 for v in q]
[True, True, True, True, True, True, True, True]
Return the bounded edges (excluding rays and lines).
OUTPUT:
A generator for pairs of vertices, one pair per edge.
EXAMPLES:
sage: p = Polyhedron(vertices=[[1,0],[0,1]], rays=[[1,0],[0,1]])
sage: [ e for e in p.bounded_edges() ]
[(A vertex at (0, 1), A vertex at (1, 0))]
sage: for e in p.bounded_edges(): print e
(A vertex at (0, 1), A vertex at (1, 0))
Return the coordinates of a rectangular box containing the non-empty polytope.
INPUT:
OUTPUT:
A pair of tuples (box_min, box_max) where box_min are the coordinates of a point bounding the coordinates of the polytope from below and box_max bounds the coordinates from above.
EXAMPLES:
sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box()
((1/3, 1/3), (2/3, 2/3))
sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral=True)
((0, 0), (1, 1))
sage: polytopes.buckyball().bounding_box()
((-1059/1309, -1059/1309, -1059/1309), (1059/1309, 1059/1309, 1059/1309))
Write the inequalities/equations data of the polyhedron in cdd’s H-representation format.
OUTPUT:
A string. If you save the output to filename.ine then you can run the stand-alone cdd via cddr+ filename.ine
EXAMPLES:
sage: p = polytopes.n_cube(2)
sage: print p.cdd_Hrepresentation()
H-representation
begin
4 3 rational
1 1 0
1 0 1
1 -1 0
1 0 -1
end
Write the vertices/rays/lines data of the polyhedron in cdd’s V-representation format.
OUTPUT:
A string. If you save the output to filename.ext then you can run the stand-alone cdd via cddr+ filename.ext
EXAMPLES:
sage: q = Polyhedron(vertices = [[1,1],[0,0],[1,0],[0,1]])
sage: print q.cdd_Vrepresentation()
V-representation
begin
4 3 rational
1 0 0
1 0 1
1 1 0
1 1 1
end
Return the average of the vertices.
See also interior_point().
OUTPUT:
The center of the polyhedron. All rays and lines are ignored. Raises a ZeroDivisionError for the empty polytope.
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: p = p + vector([1,0,0])
sage: p.center()
(1, 0, 0)
Computes the combinatorial automorphism group of the vertex graph of the polyhedron.
OUTPUT:
A PermutationGroup that is isomorphic to the combinatorial automorphism group is returned.
Note that in Sage, permutation groups always act on positive integers while self.Vrepresentation() is indexed by nonnegative integers. The indexing of the permutation group is chosen to be shifted by +1. That is, i in the permutation group corresponds to the V-representation object self.Vrepresentation(i-1).
EXAMPLES:
sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
sage: quadrangle.combinatorial_automorphism_group()
Permutation Group with generators [(2,3), (1,2)(3,4)]
sage: quadrangle.restricted_automorphism_group()
Permutation Group with generators [()]
Permutations can only exchange vertices with vertices, rays with rays, and lines with lines:
sage: P = Polyhedron(vertices=[(1,0,0), (1,1,0)], rays=[(1,0,0)], lines=[(0,0,1)])
sage: P.combinatorial_automorphism_group()
Permutation Group with generators [(3,4)]
Test whether the polyhedron contains the given point.
See also interior_contains() and relative_interior_contains().
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: P = Polyhedron(vertices=[[1,1],[1,-1],[0,0]])
sage: P.contains( [1,0] )
True
sage: P.contains( P.center() ) # true for any convex set
True
As a shorthand, one may use the usual in operator:
sage: P.center() in P
True
sage: [-1,-1] in P
False
The point need not have coordinates in the same field as the polyhedron:
sage: ray = Polyhedron(vertices=[(0,0)], rays=[(1,0)], base_ring=QQ)
sage: ray.contains([sqrt(2)/3,0]) # irrational coordinates are ok
True
sage: a = var('a')
sage: ray.contains([a,0]) # a might be negative!
False
sage: assume(a>0)
sage: ray.contains([a,0])
True
sage: ray.contains(['hello', 'kitty']) # no common ring for coordinates
False
The empty polyhedron needs extra care, see trac #10238:
sage: empty = Polyhedron(); empty
The empty polyhedron in ZZ^0
sage: empty.contains([])
False
sage: empty.contains([0]) # not a point in QQ^0
False
sage: full = Polyhedron(vertices=[()]); full
A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex
sage: full.contains([])
True
sage: full.contains([0])
False
Return the convex hull of the set-theoretic union of the two polyhedra.
INPUT:
OUTPUT:
The convex hull.
EXAMPLES:
sage: a_simplex = polytopes.n_simplex(3)
sage: verts = a_simplex.vertices()
sage: verts = [[x[0]*3/5+x[1]*4/5, -x[0]*4/5+x[1]*3/5, x[2]] for x in verts]
sage: another_simplex = Polyhedron(vertices = verts)
sage: simplex_union = a_simplex.convex_hull(another_simplex)
sage: simplex_union.n_vertices()
7
Delete this polyhedron.
This speeds up creation of new polyhedra by reusing objects. After recycling a polyhedron object, it is not in a consistent state any more and neither the polyhedron nor its H/V-representation objects may be used any more.
See also
recycle()
EXAMPLES:
sage: p = Polyhedron([(0,0),(1,0),(0,1)])
sage: p.delete()
sage: vertices = [(0,0,0,0),(1,0,0,0),(0,1,0,0),(1,1,0,0),(0,0,1,0),(0,0,0,1)]
sage: def loop_polyhedra():
... for i in range(0,100):
... p = Polyhedron(vertices)
sage: timeit('loop_polyhedra()') # not tested - random
5 loops, best of 3: 79.5 ms per loop
sage: def loop_polyhedra_with_recycling():
... for i in range(0,100):
... p = Polyhedron(vertices)
... p.delete()
sage: timeit('loop_polyhedra_with_recycling()') # not tested - random
5 loops, best of 3: 57.3 ms per loop
Return the dilated (uniformly stretched) polyhedron.
INPUT:
OUTPUT:
The polyhedron dilated by that scalar, possibly coerced to a bigger field.
EXAMPLES:
sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in srange(2,6)])
sage: p.vertex_generator().next()
A vertex at (2, 4, 8)
sage: p2 = p.dilation(2)
sage: p2.vertex_generator().next()
A vertex at (4, 8, 16)
sage: p.dilation(2) == p * 2
True
TESTS:
Dilation of empty polyhedrons works, see trac ticket #14987:
sage: p = Polyhedron(ambient_dim=2); p
The empty polyhedron in ZZ^2
sage: p.dilation(3)
The empty polyhedron in ZZ^2
TESTS:
sage: p = Polyhedron(vertices=[(1,1)], rays=[(1,0)], lines=[(0,1)])
sage: (-p).rays()
(A ray in the direction (-1, 0),)
sage: (-p).lines()
(A line in the direction (0, 1),)
sage: (0*p).rays()
()
sage: (0*p).lines()
()
Return the dimension of the polyhedron.
OUTPUT:
-1 if the polyhedron is empty, otherwise a non-negative integer.
EXAMPLES:
sage: simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]])
sage: simplex.dim()
3
sage: simplex.ambient_dim()
4
The empty set is a special case (Trac #12193):
sage: P1=Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]])
sage: P2=Polyhedron(vertices=[[2,0,0],[0,2,0],[0,0,2]])
sage: P12 = P1.intersection(P2)
sage: P12
The empty polyhedron in ZZ^3
sage: P12.dim()
-1
Return the dimension of the polyhedron.
OUTPUT:
-1 if the polyhedron is empty, otherwise a non-negative integer.
EXAMPLES:
sage: simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]])
sage: simplex.dim()
3
sage: simplex.ambient_dim()
4
The empty set is a special case (Trac #12193):
sage: P1=Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]])
sage: P2=Polyhedron(vertices=[[2,0,0],[0,2,0],[0,0,2]])
sage: P12 = P1.intersection(P2)
sage: P12
The empty polyhedron in ZZ^3
sage: P12.dim()
-1
Return a new polyhedron formed from two points on each edge between two vertices.
INPUT:
Default is \(\frac{1}{3}\).
OUTPUT:
A Polyhedron object, truncated as described above.
EXAMPLES:
sage: cube = polytopes.n_cube(3)
sage: trunc_cube = cube.edge_truncation()
sage: trunc_cube.n_vertices()
24
sage: trunc_cube.n_inequalities()
14
Return a generator for the linear equations satisfied by the polyhedron.
EXAMPLES:
sage: p = polytopes.regular_polygon(8,base_ring=RDF)
sage: p3 = Polyhedron(vertices = [x+[0] for x in p.vertices()], base_ring=RDF)
sage: p3.equation_generator().next()
An equation (0.0, 0.0, 1.0) x + 0.0 == 0
Return all linear constraints of the polyhedron.
OUTPUT:
A tuple of equations.
EXAMPLES:
sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
sage: test_p.equations()
(An equation (1, 1, 1, 1) x - 10 == 0,)
Return the linear constraints of the polyhedron. As with inequalities, each constraint is given as [b -a1 -a2 ... an] where for variables x1, x2,..., xn, the polyhedron satisfies the equation b = a1*x1 + a2*x2 + ... + an*xn.
Note
It is recommended to use equations() or equation_generator() instead to iterate over the list of Equation objects.
EXAMPLES:
sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
sage: test_p.equations_list()
[[-10, 1, 1, 1, 1]]
Return the f-vector.
OUTPUT:
Returns a vector whose i-th entry is the number of i-dimensional faces of the polytope.
EXAMPLES:
sage: p = Polyhedron(vertices=[[1, 2, 3], [1, 3, 2],
... [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [0, 0, 0]])
sage: p.f_vector()
(1, 7, 12, 7, 1)
Return the face-lattice poset.
OUTPUT:
A FinitePoset. Elements are given as PolyhedronFace.
In the case of a full-dimensional polytope, the faces are pairs (vertices, inequalities) of the spanning vertices and corresponding saturated inequalities. In general, a face is defined by a pair (V-rep. objects, H-rep. objects). The V-representation objects span the face, and the corresponding H-representation objects are those inequalities and equations that are saturated on the face.
The bottom-most element of the face lattice is the “empty face”. It contains no V-representation object. All H-representation objects are incident.
The top-most element is the “full face”. It is spanned by all V-representation objects. The incident H-representation objects are all equations and no inequalities.
In the case of a full-dimensional polytope, the “empty face” and the “full face” are the empty set (no vertices, all inequalities) and the full polytope (all vertices, no inequalities), respectively.
ALGORITHM:
For a full-dimensional polytope, the basic algorithm is described in Hasse_diagram_from_incidences(). There are three generalizations of [KP2002] necessary to deal with more general polytopes, corresponding to the extra H/V-representation objects:
EXAMPLES:
sage: square = polytopes.n_cube(2)
sage: square.face_lattice()
Finite poset containing 10 elements
sage: list(_)
[<>, <0>, <1>, <2>, <3>, <0,1>, <0,2>, <2,3>, <1,3>, <0,1,2,3>]
sage: poset_element = _[6]
sage: a_face = poset_element
sage: a_face
<0,2>
sage: a_face.dim()
1
sage: set(a_face.ambient_Vrepresentation()) == ... set([square.Vrepresentation(0), square.Vrepresentation(2)])
True
sage: a_face.ambient_Vrepresentation()
(A vertex at (-1, -1), A vertex at (1, -1))
sage: a_face.ambient_Hrepresentation()
(An inequality (0, 1) x + 1 >= 0,)
A more complicated example:
sage: c5_10 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] for i in range(1,11)])
sage: c5_10_fl = c5_10.face_lattice()
sage: [len(x) for x in c5_10_fl.level_sets()]
[1, 10, 45, 100, 105, 42, 1]
Note that if the polyhedron contains lines then there is a dimension gap between the empty face and the first non-empty face in the face lattice:
sage: line = Polyhedron(vertices=[(0,)], lines=[(1,)])
sage: [ fl.dim() for fl in line.face_lattice() ]
[-1, 1]
TESTS:
sage: c5_20 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5]
... for i in range(1,21)])
sage: c5_20_fl = c5_20.face_lattice() # long time
sage: [len(x) for x in c5_20_fl.level_sets()] # long time
[1, 20, 190, 580, 680, 272, 1]
sage: polytopes.n_cube(2).face_lattice().plot()
sage: level_sets = polytopes.cross_polytope(2).face_lattice().level_sets()
sage: print level_sets[0], level_sets[-1]
[<>] [<0,1,2,3>]
Various degenerate polyhedra:
sage: Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0]]).face_lattice().level_sets()
[[<>], [<0>, <1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]]
sage: Polyhedron(vertices=[(1,0,0),(0,1,0)], rays=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]]
sage: Polyhedron(rays=[(1,0,0),(0,1,0)], vertices=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<0>], [<0,1>, <0,2>], [<0,1,2>]]
sage: Polyhedron(rays=[(1,0),(0,1)], vertices=[(0,0)]).face_lattice().level_sets()
[[<>], [<0>], [<0,1>, <0,2>], [<0,1,2>]]
sage: Polyhedron(vertices=[(1,),(0,)]).face_lattice().level_sets()
[[<>], [<0>, <1>], [<0,1>]]
sage: Polyhedron(vertices=[(1,0,0),(0,1,0)], lines=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<0,1>, <0,2>], [<0,1,2>]]
sage: Polyhedron(lines=[(1,0,0)], vertices=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<0,1>]]
sage: Polyhedron(lines=[(1,0),(0,1)], vertices=[(0,0)]).face_lattice().level_sets()
[[<>], [<0,1,2>]]
sage: Polyhedron(lines=[(1,0)], rays=[(0,1)], vertices=[(0,0)]) ... .face_lattice().level_sets()
[[<>], [<0,1>], [<0,1,2>]]
sage: Polyhedron(vertices=[(0,)], lines=[(1,)]).face_lattice().level_sets()
[[<>], [<0,1>]]
sage: Polyhedron(lines=[(1,0)], vertices=[(0,0)]).face_lattice().level_sets()
[[<>], [<0,1>]]
REFERENCES:
[KP2002] | Volker Kaibel and Marc E. Pfetsch, “Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences”, Computational Geometry: Theory and Applications, Volume 23, Issue 3 (November 2002), 281-290. Available at http://portal.acm.org/citation.cfm?id=763203 and free of charge at http://arxiv.org/abs/math/0106043 |
Return the faces of given dimension
INPUT:
OUTPUT:
A tuple of PolyhedronFace. See face for details. The order random but fixed.
EXAMPLES:
Here we find the vertex and face indices of the eight three-dimensional facets of the four-dimensional hypercube:
sage: p = polytopes.n_cube(4)
sage: p.faces(3)
(<0,1,2,3,4,5,6,7>, <0,1,2,3,8,9,10,11>, <0,1,4,5,8,9,12,13>,
<0,2,4,6,8,10,12,14>, <2,3,6,7,10,11,14,15>, <8,9,10,11,12,13,14,15>,
<4,5,6,7,12,13,14,15>, <1,3,5,7,9,11,13,15>)
sage: face = p.faces(3)[0]
sage: face.ambient_Hrepresentation()
(An inequality (1, 0, 0, 0) x + 1 >= 0,)
sage: face.vertices()
(A vertex at (-1, -1, -1, -1), A vertex at (-1, -1, -1, 1),
A vertex at (-1, -1, 1, -1), A vertex at (-1, -1, 1, 1),
A vertex at (-1, 1, -1, -1), A vertex at (-1, 1, -1, 1),
A vertex at (-1, 1, 1, -1), A vertex at (-1, 1, 1, 1))
You can use the index() method to enumerate vertices and inequalities:
sage: def get_idx(rep): return rep.index()
sage: map(get_idx, face.ambient_Hrepresentation())
[4]
sage: map(get_idx, face.ambient_Vrepresentation())
[0, 1, 2, 3, 4, 5, 6, 7]
sage: [ (map(get_idx, face.ambient_Vrepresentation()), map(get_idx, face.ambient_Hrepresentation()))
... for face in p.faces(3) ]
[([0, 1, 2, 3, 4, 5, 6, 7], [4]),
([0, 1, 2, 3, 8, 9, 10, 11], [5]),
([0, 1, 4, 5, 8, 9, 12, 13], [6]),
([0, 2, 4, 6, 8, 10, 12, 14], [7]),
([2, 3, 6, 7, 10, 11, 14, 15], [2]),
([8, 9, 10, 11, 12, 13, 14, 15], [0]),
([4, 5, 6, 7, 12, 13, 14, 15], [1]),
([1, 3, 5, 7, 9, 11, 13, 15], [3])]
TESTS:
sage: pr = Polyhedron(rays = [[1,0,0],[-1,0,0],[0,1,0]], vertices = [[-1,-1,-1]], lines=[(0,0,1)])
sage: pr.faces(4)
()
sage: pr.faces(3)
(<0,1,2,3>,)
sage: pr.faces(2)
(<0,1,2>,)
sage: pr.faces(1)
()
sage: pr.faces(0)
()
sage: pr.faces(-1)
()
Return the adjacency matrix for the facets and hyperplanes.
EXAMPLES:
sage: polytopes.n_simplex(4).facet_adjacency_matrix()
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
Return the list of face indices (i.e. indices of H-representation objects) and the indices of faces adjacent to them.
Note
Instead of working with face indices, it is recommended that you use the H-representation objects directly (see example).
EXAMPLES:
sage: p = polytopes.permutahedron(4)
sage: p.facial_adjacencies()[0:3]
doctest:...: DeprecationWarning:
This method is deprecated.
Use self.Hrepresentation(i).neighbors() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [1, 2, 5, 10, 12, 13]], [1, [0, 2, 5, 7, 9, 11]], [2, [0, 1, 10, 11]]]
sage: f0 = p.Hrepresentation(0)
sage: f0.index() == 0
True
sage: f0_adjacencies = [f0.index(), [n.index() for n in f0.neighbors()]]
sage: p.facial_adjacencies()[0] == f0_adjacencies
True
Return the face-vertex incidences in the form \([f_i, [v_{i_0}, v_{i_1},\dots ,v_{i_2}]]\).
Note
Instead of working with face/vertex indices, it is recommended that you use the H-representation/V-representation objects directly (see examples). Or use incidence_matrix().
OUTPUT:
The face indices are the indices of the H-representation objects, and the vertex indices are the indices of the V-representation objects.
EXAMPLES:
sage: p = Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[0,0,0],[2,2,5]])
sage: p.facial_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Hrepresentation(i).incident() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [0, 1, 3, 4]],
[1, [0, 1, 2]],
[2, [0, 2, 3]],
[3, [2, 3, 4]],
[4, [1, 2, 4]]]
sage: f0 = p.Hrepresentation(0)
sage: f0.index() == 0
True
sage: f0_incidences = [f0.index(), [v.index() for v in f0.incident()]]
sage: p.facial_incidences()[0] == f0_incidences
True
sage: p.incidence_matrix().column(0)
(1, 1, 0, 1, 1)
sage: p.incidence_matrix().column(1)
(1, 1, 1, 0, 0)
sage: p.incidence_matrix().column(2)
(1, 0, 1, 1, 0)
sage: p.incidence_matrix().column(3)
(0, 0, 1, 1, 1)
sage: p.incidence_matrix().column(4)
(0, 1, 1, 0, 1)
Return the base ring.
OUTPUT:
Either QQ (exact arithmetic using gmp, default) or RDF (double precision floating-point arithmetic)
EXAMPLES:
sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]])
sage: triangle.base_ring() == ZZ
True
Return the Gale transform of a polytope as described in the reference below.
OUTPUT:
A list of vectors, the Gale transform. The dimension is the dimension of the affine dependencies of the vertices of the polytope.
EXAMPLES:
This is from the reference, for a triangular prism:
sage: p = Polyhedron(vertices = [[0,0],[0,1],[1,0]])
sage: p2 = p.prism()
sage: p2.gale_transform()
[(1, 0), (0, 1), (-1, -1), (-1, 0), (0, -1), (1, 1)]
REFERENCES:
Lectures in Geometric Combinatorics, R.R.Thomas, 2006, AMS Press.
Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.
EXAMPLES:
sage: g3 = polytopes.n_cube(3).vertex_graph()
sage: len(g3.automorphism_group())
48
sage: s4 = polytopes.n_simplex(4).vertex_graph()
sage: s4.is_eulerian()
True
Return the hyperplane arrangement defined by the equations and inequalities.
OUTPUT:
A hyperplane arrangement consisting of the hyperplanes defined by the Hrepresentation(). If the polytope is full-dimensional, this is the hyperplane arrangement spanned by the facets of the polyhedron.
EXAMPLES:
sage: p = polytopes.n_cube(2)
sage: p.hyperplane_arrangement()
Arrangement <-t0 + 1 | -t1 + 1 | t1 + 1 | t0 + 1>
Deprecated. Alias for inequalities()
EXAMPLES:
sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: p3.ieqs() == p3.inequalities()
doctest:...: DeprecationWarning:
This method is deprecated. Use inequalities() instead.
See http://trac.sagemath.org/11763 for details.
True
Return the incidence matrix.
Note
The columns correspond to inequalities/equations in the order Hrepresentation(), the rows correspond to vertices/rays/lines in the order Vrepresentation()
EXAMPLES:
sage: p = polytopes.cuboctahedron()
sage: p.incidence_matrix()
[0 0 1 1 0 1 0 0 0 0 1 0 0 0]
[0 0 0 1 0 0 1 0 1 0 1 0 0 0]
[0 0 1 1 1 0 0 1 0 0 0 0 0 0]
[1 0 0 1 1 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 1 1 1 0 0 0]
[0 0 1 0 0 1 0 1 0 0 0 1 0 0]
[1 0 0 0 0 0 1 0 1 0 0 0 1 0]
[1 0 0 0 1 0 0 1 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 1 0 1 0 0]
[0 1 0 0 0 0 0 0 1 1 0 0 1 0]
[0 1 0 0 0 0 0 1 0 0 0 1 0 1]
[1 1 0 0 0 0 0 0 0 0 0 0 1 1]
sage: v = p.Vrepresentation(0)
sage: v
A vertex at (-1/2, -1/2, 0)
sage: h = p.Hrepresentation(2)
sage: h
An inequality (1, 1, -1) x + 1 >= 0
sage: h.eval(v) # evaluation (1, 1, -1) * (-1/2, -1/2, 0) + 1
0
sage: h*v # same as h.eval(v)
0
sage: p.incidence_matrix() [0,2] # this entry is (v,h)
1
sage: h.contains(v)
True
sage: p.incidence_matrix() [2,0] # note: not symmetric
0
Return all inequalities.
OUTPUT:
A tuple of inequalities.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0,0],[0,0,1],[0,1,0],[1,0,0],[2,2,2]])
sage: p.inequalities()[0:3]
(An inequality (1, 0, 0) x + 0 >= 0,
An inequality (0, 1, 0) x + 0 >= 0,
An inequality (0, 0, 1) x + 0 >= 0)
sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: ieqs = p3.inequalities()
sage: ieqs[0]
An inequality (0, 1, 1, 1) x - 6 >= 0
sage: list(_)
[-6, 0, 1, 1, 1]
Return a list of inequalities as coefficient lists.
Note
It is recommended to use inequalities() or inequality_generator() instead to iterate over the list of Inequality objects.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0,0],[0,0,1],[0,1,0],[1,0,0],[2,2,2]])
sage: p.inequalities_list()[0:3]
[[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: ieqs = p3.inequalities_list()
sage: ieqs[0]
[-6, 0, 1, 1, 1]
sage: ieqs[-1]
[-3, 0, 1, 0, 1]
sage: ieqs == [list(x) for x in p3.inequality_generator()]
True
Return a generator for the defining inequalities of the polyhedron.
OUTPUT:
A generator of the inequality Hrepresentation objects.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: for v in triangle.inequality_generator(): print(v)
An inequality (1, 1) x - 1 >= 0
An inequality (0, -1) x + 1 >= 0
An inequality (-1, 0) x + 1 >= 0
sage: [ v for v in triangle.inequality_generator() ]
[An inequality (1, 1) x - 1 >= 0,
An inequality (0, -1) x + 1 >= 0,
An inequality (-1, 0) x + 1 >= 0]
sage: [ [v.A(), v.b()] for v in triangle.inequality_generator() ]
[[(1, 1), -1], [(0, -1), 1], [(-1, 0), 1]]
Return the integral points in the polyhedron.
Uses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.
INPUT:
OUTPUT:
The list of integral points in the polyhedron. If the polyhedron is not compact, a ValueError is raised.
EXAMPLES:
sage: Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)]).integral_points()
((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))
sage: simplex = Polyhedron([(1,2,3), (2,3,7), (-2,-3,-11)])
sage: simplex.integral_points()
((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))
The polyhedron need not be full-dimensional:
sage: simplex = Polyhedron([(1,2,3,5), (2,3,7,5), (-2,-3,-11,5)])
sage: simplex.integral_points()
((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))
sage: point = Polyhedron([(2,3,7)])
sage: point.integral_points()
((2, 3, 7),)
sage: empty = Polyhedron()
sage: empty.integral_points()
()
Here is a simplex where the naive algorithm of running over all points in a rectangular bounding box no longer works fast enough:
sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
sage: simplex = Polyhedron(v); simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices
sage: len(simplex.integral_points())
49
Finally, the 3-d reflexive polytope number 4078:
sage: v = [(1,0,0), (0,1,0), (0,0,1), (0,0,-1), (0,-2,1),
... (-1,2,-1), (-1,2,-2), (-1,1,-2), (-1,-1,2), (-1,-3,2)]
sage: P = Polyhedron(v)
sage: pts1 = P.integral_points() # Sage's own code
sage: all(P.contains(p) for p in pts1)
True
sage: pts2 = LatticePolytope(v).points_pc() # PALP
sage: for p in pts1: p.set_immutable()
sage: set(pts1) == set(pts2)
True
sage: timeit('Polyhedron(v).integral_points()') # not tested - random
625 loops, best of 3: 1.41 ms per loop
sage: timeit('LatticePolytope(v).points()') # not tested - random
25 loops, best of 3: 17.2 ms per loop
Test whether the interior of the polyhedron contains the given point.
See also contains() and relative_interior_contains().
INPUT:
OUTPUT:
True or False.
EXAMPLES:
sage: P = Polyhedron(vertices=[[0,0],[1,1],[1,-1]])
sage: P.contains( [1,0] )
True
sage: P.interior_contains( [1,0] )
False
If the polyhedron is of strictly smaller dimension than the ambient space, its interior is empty:
sage: P = Polyhedron(vertices=[[0,1],[0,-1]])
sage: P.contains( [0,0] )
True
sage: P.interior_contains( [0,0] )
False
The empty polyhedron needs extra care, see trac #10238:
sage: empty = Polyhedron(); empty
The empty polyhedron in ZZ^0
sage: empty.interior_contains([])
False
Return the intersection of one polyhedron with another.
INPUT:
- other – a Polyhedron.
OUTPUT:
The intersection.
Note that the intersection of two \(\ZZ\)-polyhedra might not be a \(\ZZ\)-polyhedron. In this case, a \(\QQ\)-polyhedron is returned.
EXAMPLES:
sage: cube = polytopes.n_cube(3) sage: oct = polytopes.cross_polytope(3) sage: cube.intersection(oct*2) A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
As a shorthand, one may use:
sage: cube & oct*2
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
The intersection of two \(\ZZ\)-polyhedra is not necessarily a \(\ZZ\)-polyhedron:
sage: P = Polyhedron([(0,0),(1,1)], base_ring=ZZ)
sage: P.intersection(P)
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: Q = Polyhedron([(0,1),(1,0)], base_ring=ZZ)
sage: P.intersection(Q)
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex
sage: _.Vrepresentation()
(A vertex at (1/2, 1/2),)
Test whether Y is a Minkowski summand.
See Minkowski_sum().
OUTPUT:
Boolean. Whether there exists another polyhedron \(Z\) such that self can be written as \(Y\oplus Z\).
EXAMPLES:
sage: A = polytopes.n_cube(2)
sage: B = Polyhedron(vertices=[(0,1), (1/2,1)])
sage: C = Polyhedron(vertices=[(1,1)])
sage: A.is_Minkowski_summand(B)
True
sage: A.is_Minkowski_summand(C)
True
sage: B.is_Minkowski_summand(C)
True
sage: B.is_Minkowski_summand(A)
False
sage: C.is_Minkowski_summand(A)
False
sage: C.is_Minkowski_summand(B)
False
Test for boundedness of the polytope.
EXAMPLES:
sage: p = polytopes.icosahedron()
sage: p.is_compact()
True
sage: p = Polyhedron(ieqs = [[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,-1,0,0]])
sage: p.is_compact()
False
Test whether the polyhedron is the empty polyhedron
OUTPUT:
Boolean.
EXAMPLES:
sage: P = Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]]); P
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: P.is_empty(), P.is_universe()
(False, False)
sage: Q = Polyhedron(vertices=()); Q
The empty polyhedron in ZZ^0
sage: Q.is_empty(), Q.is_universe()
(True, False)
sage: R = Polyhedron(lines=[(1,0),(0,1)]); R
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines
sage: R.is_empty(), R.is_universe()
(False, True)
Return whether the polyhedron is full dimensional.
OUTPUT:
Boolean. Whether the polyhedron is not contained in any strict affine subspace.
EXAMPLES:
sage: polytopes.n_cube(3).is_full_dimensional()
True
sage: Polyhedron(vertices=[(1,2,3)], rays=[(1,0,0)]).is_full_dimensional()
False
Return whether the polyhedron is a lattice polytope.
OUTPUT:
True if the polyhedron is compact and has only integral vertices, False otherwise.
EXAMPLES:
sage: polytopes.cross_polytope(3).is_lattice_polytope()
True
sage: polytopes.regular_polygon(5).is_lattice_polytope()
False
Test for simplicity of a polytope.
See Wikipedia article Simple_polytope
EXAMPLES:
sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]])
sage: p.is_simple()
True
sage: p = Polyhedron([[0,0,0],[4,4,0],[4,0,0],[0,4,0],[2,2,2]])
sage: p.is_simple()
False
Return whether the polyhedron is a simplex.
EXAMPLES:
sage: Polyhedron([(0,0,0), (1,0,0), (0,1,0)]).is_simplex()
True
sage: polytopes.n_simplex(3).is_simplex()
True
sage: polytopes.n_cube(3).is_simplex()
False
Tests if the polytope is simplicial
A polytope is simplicial if every facet is a simplex.
See Wikipedia article Simplicial_polytope
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: p.is_simplicial()
False
sage: q = polytopes.n_simplex(5)
sage: q.is_simplicial()
True
sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]])
sage: p.is_simplicial()
True
sage: q = Polyhedron([[1,1,1],[-1,1,1],[1,-1,1],[-1,-1,1],[1,1,-1]])
sage: q.is_simplicial()
False
The method is not implemented for unbounded polyhedra:
sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
sage: p.is_simplicial()
Traceback (most recent call last):
...
NotImplementedError: This function is implemented for polytopes only.
Test whether the polyhedron is the whole ambient space
OUTPUT:
Boolean.
EXAMPLES:
sage: P = Polyhedron(vertices=[[1,0,0],[0,1,0],[0,0,1]]); P
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: P.is_empty(), P.is_universe()
(False, False)
sage: Q = Polyhedron(vertices=()); Q
The empty polyhedron in ZZ^0
sage: Q.is_empty(), Q.is_universe()
(True, False)
sage: R = Polyhedron(lines=[(1,0),(0,1)]); R
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines
sage: R.is_empty(), R.is_universe()
(False, True)
Return an encompassing lattice polytope.
INPUT:
OUTPUT:
A LatticePolytope. If the polyhedron is compact and has integral vertices, the lattice polytope equals the polyhedron. If the polyhedron is compact but has at least one non-integral vertex, a strictly larger lattice polytope is returned.
If the polyhedron is not compact, a NotImplementedError is raised.
If the polyhedron is not integral and envelope=False, a ValueError is raised.
ALGORITHM:
For each non-integral vertex, a bounding box of integral points is added and the convex hull of these integral points is returned.
EXAMPLES:
First, a polyhedron with integral vertices:
sage: P = Polyhedron( vertices = [(1, 0), (0, 1), (-1, 0), (0, -1)])
sage: lp = P.lattice_polytope(); lp
2-d reflexive polytope #3 in 2-d lattice M
sage: lp.vertices_pc()
M(-1, 0),
M( 0, -1),
M( 0, 1),
M( 1, 0)
in 2-d lattice M
Here is a polyhedron with non-integral vertices:
sage: P = Polyhedron( vertices = [(1/2, 1/2), (0, 1), (-1, 0), (0, -1)])
sage: lp = P.lattice_polytope()
Traceback (most recent call last):
...
ValueError: Some vertices are not integral. You probably want
to add the argument "envelope=True" to compute an enveloping
lattice polytope.
sage: lp = P.lattice_polytope(True); lp
2-d reflexive polytope #5 in 2-d lattice M
sage: lp.vertices_pc()
M(-1, 0),
M( 0, -1),
M( 0, 1),
M( 1, 0),
M( 1, 1)
in 2-d lattice M
Return a generator for the lines of the polyhedron.
EXAMPLES:
sage: pr = Polyhedron(rays = [[1,0],[-1,0],[0,1]], vertices = [[-1,-1]])
sage: pr.line_generator().next().vector()
(1, 0)
Deprecated. Use equations() instead. Returns the linear constraints of the polyhedron. As with inequalities, each constraint is given as [b -a1 -a2 ... an] where for variables x1, x2,..., xn, the polyhedron satisfies the equation b = a1*x1 + a2*x2 + ... + an*xn.
EXAMPLES:
sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
sage: test_p.linearities()
doctest:...: DeprecationWarning:
This method is deprecated. Use equations_list() instead.
See http://trac.sagemath.org/11763 for details.
[[-10, 1, 1, 1, 1]]
sage: test_p.linearities() == test_p.equations_list()
True
Return all lines of the polyhedron.
OUTPUT:
A tuple of lines.
EXAMPLES:
sage: p = Polyhedron(rays = [[1,0],[-1,0],[0,1],[1,1]], vertices = [[-2,-2],[2,3]])
sage: p.lines()
(A line in the direction (1, 0),)
Return a list of lines of the polyhedron. The line data is given as a list of coordinates rather than as a Hrepresentation object.
Note
It is recommended to use line_generator() instead to iterate over the list of Line objects.
EXAMPLES:
sage: p = Polyhedron(rays = [[1,0],[-1,0],[0,1],[1,1]], vertices = [[-2,-2],[2,3]])
sage: p.lines_list()
[[1, 0]]
sage: p.lines_list() == [list(x) for x in p.line_generator()]
True
Computes the volume of a polytope using lrs.
OUTPUT:
The volume, cast to RDF (although lrs seems to output a rational value this must be an approximation in some cases).
EXAMPLES:
sage: polytopes.n_cube(3).lrs_volume() #optional - lrs
doctest:...: DeprecationWarning: use volume(engine='lrs') instead
See http://trac.sagemath.org/13249 for details.
8.0
sage: (polytopes.n_cube(3)*2).lrs_volume() #optional - lrs
64.0
sage: polytopes.twenty_four_cell().lrs_volume() #optional - lrs
2.0
REFERENCES:
David Avis’s lrs program.
Return the number of objects that make up the H-representation of the polyhedron.
OUTPUT:
Integer.
EXAMPLES:
sage: p = polytopes.cross_polytope(4)
sage: p.n_Hrepresentation()
16
sage: p.n_Hrepresentation() == p.n_inequalities() + p.n_equations()
True
Return the number of objects that make up the V-representation of the polyhedron.
OUTPUT:
Integer.
EXAMPLES:
sage: p = polytopes.n_simplex(4)
sage: p.n_Vrepresentation()
5
sage: p.n_Vrepresentation() == p.n_vertices() + p.n_rays() + p.n_lines()
True
Return the number of equations. The representation will always be minimal, so the number of equations is the codimension of the polyhedron in the ambient space.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
sage: p.n_equations()
1
Return the number of inequalities. The representation will always be minimal, so the number of inequalities is the number of facets of the polyhedron in the ambient space.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
sage: p.n_inequalities()
3
sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in range(6)])
sage: p.n_facets()
8
Return the number of inequalities. The representation will always be minimal, so the number of inequalities is the number of facets of the polyhedron in the ambient space.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
sage: p.n_inequalities()
3
sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in range(6)])
sage: p.n_facets()
8
Return the number of lines. The representation will always be minimal.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0]], rays=[[0,1],[0,-1]])
sage: p.n_lines()
1
Return the number of rays. The representation will always be minimal.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0],[0,1]], rays=[[1,1]])
sage: p.n_rays()
1
Return the number of vertices. The representation will always be minimal.
EXAMPLES:
sage: p = Polyhedron(vertices = [[1,0],[0,1],[1,1]], rays=[[1,1]])
sage: p.n_vertices()
2
Return a graphical representation.
INPUT:
OUTPUT:
A (multipart) graphics object.
EXAMPLES:
sage: square = polytopes.n_cube(2)
sage: point = Polyhedron([[1,1]])
sage: line = Polyhedron([[1,1],[2,1]])
sage: cube = polytopes.n_cube(3)
sage: hypercube = polytopes.n_cube(4)
By default, the wireframe is rendered in blue and the fill in green:
sage: square.plot()
sage: point.plot()
sage: line.plot()
sage: cube.plot()
sage: hypercube.plot()
Draw the lines in red and nothing else:
sage: square.plot(point=False, line='red', polygon=False)
sage: point.plot(point=False, line='red', polygon=False)
sage: line.plot(point=False, line='red', polygon=False)
sage: cube.plot(point=False, line='red', polygon=False)
sage: hypercube.plot(point=False, line='red', polygon=False)
Draw points in red, no lines, and a blue polygon:
sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
If we instead use the fill and wireframe options, the coloring depends on the dimension of the object:
sage: square.plot(fill='green', wireframe='red')
sage: point.plot(fill='green', wireframe='red')
sage: line.plot(fill='green', wireframe='red')
sage: cube.plot(fill='green', wireframe='red')
sage: hypercube.plot(fill='green', wireframe='red')
TESTS:
sage: for p in square.plot():
... print p.options()['rgbcolor'], p
blue Point set defined by 4 point(s)
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
green Polygon defined by 4 points
sage: for p in line.plot():
... print p.options()['rgbcolor'], p
blue Point set defined by 2 point(s)
green Line defined by 2 points
sage: for p in point.plot():
... print p.options()['rgbcolor'], p
green Point set defined by 1 point(s)
Draw the lines in red and nothing else:
sage: for p in square.plot(point=False, line='red', polygon=False):
... print p.options()['rgbcolor'], p
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points
Draw vertices in red, no lines, and a blue polygon:
sage: for p in square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
... print p.options()['rgbcolor'], p
red Point set defined by 4 point(s)
(0, 0, 1) Polygon defined by 4 points
sage: for p in line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
... print p.options()['rgbcolor'], p
red Point set defined by 2 point(s)
sage: for p in point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
... print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)
Draw in red without wireframe:
sage: for p in square.plot(wireframe=False, fill="red"):
... print p.options()['rgbcolor'], p
red Polygon defined by 4 points
sage: for p in line.plot(wireframe=False, fill="red"):
... print p.options()['rgbcolor'], p
red Line defined by 2 points
sage: for p in point.plot(wireframe=False, fill="red"):
... print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)
The projection_direction option:
sage: line3d = Polyhedron([(-1,-1,-1), (1,1,1)])
sage: print(line3d.plot(projection_direction=[2,3,4]).description())
Line defined by 2 points: [(-0.00..., 0.126...), (0.131..., -1.93...)]
Point set defined by 2 point(s): [(-0.00..., 0.126...), (0.131..., -1.93...)]
We try to draw the polytope in 2 or 3 dimensions:
sage: type(Polyhedron(ieqs=[(1,)]).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(polytopes.n_cube(1).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(polytopes.n_cube(2).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(polytopes.n_cube(3).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
In 4d a projection to 3d is used:
sage: type(polytopes.n_cube(4).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
sage: type(polytopes.n_cube(5).plot())
Traceback (most recent call last):
...
NotImplementedError: plotting of 5-dimensional polyhedra not implemented
If the polyhedron is not full-dimensional, the affine_hull() is used if necessary:
sage: type(Polyhedron([(0,), (1,)]).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(Polyhedron([(0,0), (1,1)]).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(Polyhedron([(0,0,0), (1,1,1)]).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
sage: type(Polyhedron([(0,0,0,0), (1,1,1,1)]).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
sage: type(Polyhedron([(0,0,0,0,0), (1,1,1,1,1)]).plot())
<class 'sage.plot.graphics.Graphics'>
Return the polar (dual) polytope.
The original vertices are translated so that their barycenter is at the origin, and then the vertices are used as the coefficients in the polar inequalities.
EXAMPLES:
sage: p = Polyhedron(vertices = [[0,0,1],[0,1,0],[1,0,0],[0,0,0],[1,1,1]], base_ring=QQ)
sage: p
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices
sage: p.polar()
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices
sage: cube = polytopes.n_cube(3)
sage: octahedron = polytopes.cross_polytope(3)
sage: cube_dual = cube.polar()
sage: octahedron == cube_dual
True
Return a prism of the original polyhedron.
EXAMPLES:
sage: square = polytopes.n_cube(2)
sage: cube = square.prism()
sage: cube
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: hypercube = cube.prism()
sage: hypercube.n_vertices()
16
Return the cartesian product.
INPUT:
OUTPUT:
The cartesian product of self and other with a suitable base ring to encompass the two.
EXAMPLES:
sage: P1 = Polyhedron([[0],[1]], base_ring=ZZ)
sage: P2 = Polyhedron([[0],[1]], base_ring=QQ)
sage: P1.product(P2)
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
The cartesian product is the product in the semiring of polyhedra:
sage: P1 * P1
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: P1 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P2 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: 2 * P1
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices
sage: P1 * 2.0
A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices
Return a projection object.
See also schlegel_projection() for a more interesting projection.
OUTPUT:
The identity projection. This is useful for plotting polyhedra.
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: proj = p.projection()
sage: proj
The projection of a polyhedron into 3 dimensions
Returns a polyhedron that is a pyramid over the original.
EXAMPLES:
sage: square = polytopes.n_cube(2); square
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: egyptian_pyramid = square.pyramid(); egyptian_pyramid
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 5 vertices
sage: egyptian_pyramid.n_vertices()
5
sage: for v in egyptian_pyramid.vertex_generator(): print v
A vertex at (0, -1, -1)
A vertex at (0, -1, 1)
A vertex at (0, 1, -1)
A vertex at (0, 1, 1)
A vertex at (1, 0, 0)
Return the maximal distance from the center to a vertex. All rays and lines are ignored.
OUTPUT:
The radius for a rational polyhedron is, in general, not rational. use radius_square() if you need a rational distance measure.
EXAMPLES:
sage: p = polytopes.n_cube(4)
sage: p.radius()
2
Return the square of the maximal distance from the center() to a vertex. All rays and lines are ignored.
OUTPUT:
The square of the radius, which is in field().
EXAMPLES:
sage: p = polytopes.permutahedron(4, project = False)
sage: p.radius_square()
5
Return a generator for the rays of the polyhedron.
EXAMPLES:
sage: pi = Polyhedron(ieqs = [[1,1,0],[1,0,1]])
sage: pir = pi.ray_generator()
sage: [x.vector() for x in pir]
[(1, 0), (0, 1)]
Return a list of rays of the polyhedron.
OUTPUT:
A tuple of rays.
EXAMPLES:
sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0],[1,1,0,0]])
sage: p.rays()
(A ray in the direction (1, 0, 0),
A ray in the direction (0, 1, 0),
A ray in the direction (0, 0, 1))
Return a list of rays as coefficient lists.
Note
It is recommended to use rays() or ray_generator() instead to iterate over the list of Ray objects.
OUTPUT:
A list of rays as lists of coordinates.
EXAMPLES:
sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0],[1,1,0,0]])
sage: p.rays_list()
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
sage: p.rays_list() == [list(r) for r in p.ray_generator()]
True
Test whether the relative interior of the polyhedron contains the given point.
See also contains() and interior_contains().
INPUT:
OUTPUT:
True or False.
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,0), (-1,0)])
sage: P.contains( (0,0) )
True
sage: P.interior_contains( (0,0) )
False
sage: P.relative_interior_contains( (0,0) )
True
sage: P.relative_interior_contains( (1,0) )
False
The empty polyhedron needs extra care, see trac #10238:
sage: empty = Polyhedron(); empty
The empty polyhedron in ZZ^0
sage: empty.relative_interior_contains([])
False
Return a solid rendering of a 2- or 3-d polytope.
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: p_solid = p.render_solid(opacity = .7)
sage: type(p_solid)
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
For polytopes in 2 or 3 dimensions, return the edges as a list of lines.
EXAMPLES:
sage: p = Polyhedron([[1,2,],[1,1],[0,0]])
sage: p_wireframe = p.render_wireframe()
sage: p_wireframe._objects
[Line defined by 2 points, Line defined by 2 points, Line defined by 2 points]
Return a “generic” point.
See also center().
OUTPUT:
A point as a coordinate vector. The point is chosen to be interior as far as possible. If the polyhedron is not full-dimensional, the point is in the relative interior. If the polyhedron is zero-dimensional, its single point is returned.
EXAMPLES:
sage: p = Polyhedron(vertices=[(3,2)], rays=[(1,-1)])
sage: p.representative_point()
(4, 1)
sage: p.center()
(3, 2)
sage: Polyhedron(vertices=[(3,2)]).representative_point()
(3, 2)
Return the restricted automorphism group.
First, let the linear automorphism group be the subgroup of the Euclidean group \(E(d) = GL(d,\RR) \ltimes \RR^d\) preserving the \(d\)-dimensional polyhedron. The Euclidean group acts in the usual way \(\vec{x}\mapsto A\vec{x}+b\) on the ambient space.
The restricted automorphism group is the subgroup of the linear automorphism group generated by permutations of the generators of the same type. That is, vertices can only be permuted with vertices, ray generators with ray generators, and line generators with line generators.
For example, take the first quadrant
Then the linear automorphism group is
Note that there are no translations that map the quadrant \(Q\) to itself, so the linear automorphism group is contained in the subgroup of rotations of the whole Euclidean group. The restricted automorphism group is
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 self.Vrepresentation() is indexed by nonnegative integers. The indexing of the permutation group is chosen to be shifted by +1. That is, i in the permutation group corresponds to the V-representation object self.Vrepresentation(i-1).
REFERENCES:
[BSS] | David Bremner, Mathieu Dutour Sikiric, Achill Schuermann: Polyhedral representation conversion up to symmetries. http://arxiv.org/abs/math/0702239 |
EXAMPLES:
sage: P = polytopes.cross_polytope(3)
sage: AutP = P.restricted_automorphism_group(); AutP
Permutation Group with generators [(3,4), (2,3)(4,5), (2,5), (1,2)(5,6), (1,6)]
sage: P24 = polytopes.twenty_four_cell()
sage: AutP24 = P24.restricted_automorphism_group()
sage: PermutationGroup([
... '(3,6)(4,7)(10,11)(14,15)(18,21)(19,22)',
... '(2,3)(7,8)(11,12)(13,14)(17,18)(22,23)',
... '(2,5)(3,10)(6,11)(8,17)(9,13)(12,16)(14,19)(15,22)(20,23)',
... '(2,10)(3,5)(6,12)(7,18)(9,14)(11,16)(13,19)(15,23)(20,22)',
... '(2,11)(3,12)(4,21)(5,6)(9,15)(10,16)(13,22)(14,23)(19,20)',
... '(1,2)(3,4)(6,7)(8,9)(12,13)(16,17)(18,19)(21,22)(23,24)',
... '(1,24)(2,13)(3,14)(5,9)(6,15)(10,19)(11,22)(12,23)(16,20)'
... ]) == AutP24
True
Here is the quadrant example mentioned in the beginning:
sage: P = Polyhedron(rays=[(1,0),(0,1)])
sage: P.Vrepresentation()
(A vertex at (0, 0), A ray in the direction (0, 1), A ray in the direction (1, 0))
sage: P.restricted_automorphism_group()
Permutation Group with generators [(2,3)]
Also, the polyhedron need not be full-dimensional:
sage: P = Polyhedron(vertices=[(1,2,3,4,5),(7,8,9,10,11)])
sage: P.restricted_automorphism_group()
Permutation Group with generators [(1,2)]
Translations do not change the restricted automorphism group. For example, any non-degenerate triangle has the dihedral group with 6 elements, \(D_6\), as its automorphism group:
sage: initial_points = [vector([1,0]), vector([0,1]), vector([-2,-1])]
sage: points = initial_points
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - initial_points[0] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - initial_points[1] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - 2*initial_points[1] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
Floating-point computations are supported with a simple fuzzy zero implementation:
sage: P = Polyhedron(vertices=[(1.0/3.0,0,0),(0,1.0/3.0,0),(0,0,1.0/3.0)], base_ring=RDF)
sage: P.restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
TESTS:
sage: p = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)])
sage: p.restricted_automorphism_group()
Permutation Group with generators [(2,3)]
Return the Schlegel projection.
INPUT:
OUTPUT:
A Projection object.
EXAMPLES:
sage: p = polytopes.n_cube(3)
sage: sch_proj = p.schlegel_projection()
sage: schlegel_edge_indices = sch_proj.lines
sage: schlegel_edges = [sch_proj.coordinates_of(x) for x in schlegel_edge_indices]
sage: len([x for x in schlegel_edges if x[0][0] > 0])
4
Return a graphical representation.
INPUT:
OUTPUT:
A (multipart) graphics object.
EXAMPLES:
sage: square = polytopes.n_cube(2)
sage: point = Polyhedron([[1,1]])
sage: line = Polyhedron([[1,1],[2,1]])
sage: cube = polytopes.n_cube(3)
sage: hypercube = polytopes.n_cube(4)
By default, the wireframe is rendered in blue and the fill in green:
sage: square.plot()
sage: point.plot()
sage: line.plot()
sage: cube.plot()
sage: hypercube.plot()
Draw the lines in red and nothing else:
sage: square.plot(point=False, line='red', polygon=False)
sage: point.plot(point=False, line='red', polygon=False)
sage: line.plot(point=False, line='red', polygon=False)
sage: cube.plot(point=False, line='red', polygon=False)
sage: hypercube.plot(point=False, line='red', polygon=False)
Draw points in red, no lines, and a blue polygon:
sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
If we instead use the fill and wireframe options, the coloring depends on the dimension of the object:
sage: square.plot(fill='green', wireframe='red')
sage: point.plot(fill='green', wireframe='red')
sage: line.plot(fill='green', wireframe='red')
sage: cube.plot(fill='green', wireframe='red')
sage: hypercube.plot(fill='green', wireframe='red')
TESTS:
sage: for p in square.plot():
... print p.options()['rgbcolor'], p
blue Point set defined by 4 point(s)
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
green Polygon defined by 4 points
sage: for p in line.plot():
... print p.options()['rgbcolor'], p
blue Point set defined by 2 point(s)
green Line defined by 2 points
sage: for p in point.plot():
... print p.options()['rgbcolor'], p
green Point set defined by 1 point(s)
Draw the lines in red and nothing else:
sage: for p in square.plot(point=False, line='red', polygon=False):
... print p.options()['rgbcolor'], p
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points
Draw vertices in red, no lines, and a blue polygon:
sage: for p in square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
... print p.options()['rgbcolor'], p
red Point set defined by 4 point(s)
(0, 0, 1) Polygon defined by 4 points
sage: for p in line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
... print p.options()['rgbcolor'], p
red Point set defined by 2 point(s)
sage: for p in point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
... print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)
Draw in red without wireframe:
sage: for p in square.plot(wireframe=False, fill="red"):
... print p.options()['rgbcolor'], p
red Polygon defined by 4 points
sage: for p in line.plot(wireframe=False, fill="red"):
... print p.options()['rgbcolor'], p
red Line defined by 2 points
sage: for p in point.plot(wireframe=False, fill="red"):
... print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)
The projection_direction option:
sage: line3d = Polyhedron([(-1,-1,-1), (1,1,1)])
sage: print(line3d.plot(projection_direction=[2,3,4]).description())
Line defined by 2 points: [(-0.00..., 0.126...), (0.131..., -1.93...)]
Point set defined by 2 point(s): [(-0.00..., 0.126...), (0.131..., -1.93...)]
We try to draw the polytope in 2 or 3 dimensions:
sage: type(Polyhedron(ieqs=[(1,)]).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(polytopes.n_cube(1).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(polytopes.n_cube(2).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(polytopes.n_cube(3).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
In 4d a projection to 3d is used:
sage: type(polytopes.n_cube(4).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
sage: type(polytopes.n_cube(5).plot())
Traceback (most recent call last):
...
NotImplementedError: plotting of 5-dimensional polyhedra not implemented
If the polyhedron is not full-dimensional, the affine_hull() is used if necessary:
sage: type(Polyhedron([(0,), (1,)]).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(Polyhedron([(0,0), (1,1)]).plot())
<class 'sage.plot.graphics.Graphics'>
sage: type(Polyhedron([(0,0,0), (1,1,1)]).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
sage: type(Polyhedron([(0,0,0,0), (1,1,1,1)]).plot())
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
sage: type(Polyhedron([(0,0,0,0,0), (1,1,1,1,1)]).plot())
<class 'sage.plot.graphics.Graphics'>
Return a simplicial complex from a triangulation of the polytope.
Warning: This first triangulates the polytope using triangulated_facial_incidences, and this function may fail in dimensions greater than 3, although it usually doesn’t.
OUTPUT:
A simplicial complex.
EXAMPLES:
sage: p = polytopes.cuboctahedron()
sage: sc = p.simplicial_complex()
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate().simplicial_complex() instead.
See http://trac.sagemath.org/11634 for details.
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate() instead.
See http://trac.sagemath.org/11634 for details.
sage: sc
Simplicial complex with 12 vertices and 20 facets
Return the translated polyhedron.
INPUT:
OUTPUT:
The translated polyhedron.
EXAMPLES:
sage: P = Polyhedron([[0,0],[1,0],[0,1]], base_ring=ZZ)
sage: P.translation([2,1])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
sage: P.translation( vector(QQ,[2,1]) )
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices
Returns a triangulation of the polytope.
INPUT:
The remaining keyword parameters are passed through to the PointConfiguration constructor:
OUTPUT:
A triangulation of the convex hull of the vertices as a Triangulation. The indices in the triangulation correspond to the Vrepresentation() objects.
EXAMPLES:
sage: cube = polytopes.n_cube(3)
sage: triangulation = cube.triangulate(
... engine='internal') # to make doctest independent of TOPCOM
sage: triangulation
(<0,1,2,7>, <0,1,4,7>, <0,2,4,7>, <1,2,3,7>, <1,4,5,7>, <2,4,6,7>)
sage: simplex_indices = triangulation[0]; simplex_indices
(0, 1, 2, 7)
sage: simplex_vertices = [ cube.Vrepresentation(i) for i in simplex_indices ]
sage: simplex_vertices
[A vertex at (-1, -1, -1), A vertex at (-1, -1, 1),
A vertex at (-1, 1, -1), A vertex at (1, 1, 1)]
sage: Polyhedron(simplex_vertices)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
Return a list of the form [face_index, [v_i_0, v_i_1,...,v_i_{n-1}]] where the face_index refers to the original defining inequality. For a given face, the collection of triangles formed by each list of v_i should triangulate that face.
In dimensions greater than 3, this is computed by randomly lifting each face up a dimension; this does not always work! This should eventually be fixed by using lrs or another program that computes triangulations.
EXAMPLES:
If the figure is already composed of triangles, then all is well:
sage: Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[2,2,5]]
... ).triangulated_facial_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate() instead.
See http://trac.sagemath.org/11634 for details.
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Hrepresentation(i).incident() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [0, 1, 2]], [1, [0, 1, 3]], [2, [0, 2, 3]], [3, [1, 2, 3]]]
Otherwise some faces get split up to triangles:
sage: Polyhedron(vertices = [[2,0,0],[4,1,0],[0,5,0],[5,5,0],
... [1,1,0],[0,0,1]]).triangulated_facial_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate() instead.
See http://trac.sagemath.org/11634 for details.
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Vrepresentation(i).neighbors() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [1, 2, 5]], [0, [2, 5, 3]], [0, [5, 3, 4]], [1, [0, 1, 2]],
[2, [0, 2, 3]], [3, [0, 3, 4]], [4, [0, 4, 5]], [5, [0, 1, 5]]]
Return a list of vertex indices and their adjacent vertices.
Note
Instead of working with vertex indices, you can use the V-representation objects directly (see examples).
Two V-representation objects are adjacent if they generate a (1-dimensional) face of the polyhedron. Examples are two vertices of a polytope that bound an edge, or a vertex and a ray of a polyhedron that generate a bounding half-line of the polyhedron. See vertex_adjacency_matrix() for a more detailed discussion.
OUTPUT:
The vertex indices are the indices of the V-representation objects.
EXAMPLES:
sage: permuta3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: permuta3.vertex_adjacencies()[0:3]
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Vrepresentation(i).neighbors() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [1, 2, 6]], [1, [0, 3, 7]], [2, [0, 4, 8]]]
sage: v0 = permuta3.Vrepresentation(0)
sage: v0.index() == 0
True
sage: list( v0.neighbors() )
[A vertex at (1, 2, 4, 3), A vertex at (1, 3, 2, 4), A vertex at (2, 1, 3, 4)]
sage: v0_adjacencies = [v0.index(), [v.index() for v in v0.neighbors()]]
sage: permuta3.vertex_adjacencies()[0] == v0_adjacencies
True
Return the binary matrix of vertex adjacencies.
EXAMPLES:
sage: polytopes.n_simplex(4).vertex_adjacency_matrix()
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
The rows and columns of the vertex adjacency matrix correspond to the Vrepresentation() objects: vertices, rays, and lines. The \((i,j)\) matrix entry equals \(1\) if the \(i\)-th and \(j\)-th V-representation object are adjacent.
Two vertices are adjacent if they are the endpoints of an edge, that is, a one-dimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two V-representation objects (see sage.geometry.polyhedron.constructor) to be adjacent if they together generate a one-face. There are three possible combinations:
For example, take the half-plane:
sage: half_plane = Polyhedron(ieqs=[(0,1,0)])
sage: half_plane.Hrepresentation()
(An inequality (1, 0) x + 0 >= 0,)
Its (non-unique) V-representation consists of a vertex, a ray, and a line. The only edge is spanned by the vertex and the line generator, so they are adjacent:
sage: half_plane.Vrepresentation()
(A line in the direction (0, 1), A ray in the direction (1, 0), A vertex at (0, 0))
sage: half_plane.vertex_adjacency_matrix()
[0 0 1]
[0 0 0]
[1 0 0]
In one dimension higher, that is for a half-space in 3 dimensions, there is no one-dimensional face. Hence nothing is adjacent:
sage: Polyhedron(ieqs=[(0,1,0,0)]).vertex_adjacency_matrix()
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
EXAMPLES:
In a bounded polygon, every vertex has precisely two adjacent ones:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)])
sage: for v in P.Vrep_generator():
... print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 1) A vertex at (0, 1)
(1, 0, 1, 0) A vertex at (1, 0)
(0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
... rays=[(0,1)])
sage: for v in P.Vrep_generator():
... print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 1) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 1, 0) A vertex at (1, 0)
(0, 0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 0, 1, 0) A vertex at (4, 1)
If the V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
... rays=[(0,1), (1,1)])
sage: for v in P.Vrep_generator():
... print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 0) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 0, 1) A vertex at (1, 0)
(0, 0, 0, 0, 1) A ray in the direction (1, 1)
(0, 0, 1, 1, 0) A vertex at (3, 0)
Return a generator for the vertices of the polyhedron.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: for v in triangle.vertex_generator(): print(v)
A vertex at (0, 1)
A vertex at (1, 0)
A vertex at (1, 1)
sage: v_gen = triangle.vertex_generator()
sage: v_gen.next() # the first vertex
A vertex at (0, 1)
sage: v_gen.next() # the second vertex
A vertex at (1, 0)
sage: v_gen.next() # the third vertex
A vertex at (1, 1)
sage: try: v_gen.next() # there are only three vertices
... except StopIteration: print "STOP"
STOP
sage: type(v_gen)
<type 'generator'>
sage: [ v for v in triangle.vertex_generator() ]
[A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1)]
Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.
EXAMPLES:
sage: g3 = polytopes.n_cube(3).vertex_graph()
sage: len(g3.automorphism_group())
48
sage: s4 = polytopes.n_simplex(4).vertex_graph()
sage: s4.is_eulerian()
True
Return the vertex-face incidences in the form \([v_i, [f_{i_0}, f_{i_1},\dots ,f_{i_2}]]\).
Note
Instead of working with face/vertex indices, you can use the H-representation/V-representation objects directly (see examples).
EXAMPLES:
sage: p = polytopes.n_simplex(3)
sage: p.vertex_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Vrepresentation(i).incident() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [0, 1, 2]], [1, [0, 1, 3]], [2, [0, 2, 3]], [3, [1, 2, 3]]]
sage: v0 = p.Vrepresentation(0)
sage: v0.index() == 0
True
sage: p.vertex_incidences()[0] == [ v0.index(), [h.index() for h in v0.incident()] ]
True
Return all vertices of the polyhedron.
OUTPUT:
A tuple of vertices.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: triangle.vertices()
(A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))
sage: a_simplex = Polyhedron(ieqs = [
... [0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]
... ], eqns = [[1,-1,-1,-1,-1]])
sage: a_simplex.vertices()
(A vertex at (1, 0, 0, 0), A vertex at (0, 1, 0, 0),
A vertex at (0, 0, 1, 0), A vertex at (0, 0, 0, 1))
Return a list of vertices of the polyhedron.
Note
It is recommended to use vertex_generator() instead to iterate over the list of Vertex objects.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: triangle.vertices_list()
[[0, 1], [1, 0], [1, 1]]
sage: a_simplex = Polyhedron(ieqs = [
... [0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]
... ], eqns = [[1,-1,-1,-1,-1]])
sage: a_simplex.vertices_list()
[[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
sage: a_simplex.vertices_list() == [list(v) for v in a_simplex.vertex_generator()]
True
Return the coordinates of the vertices as the columns of a matrix.
INPUT:
OUTPUT:
A matrix over base_ring whose columns are the coordinates of the vertices. A TypeError is raised if the coordinates cannot be converted to base_ring.
EXAMPLES:
sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: triangle.vertices_matrix()
[0 1 1]
[1 0 1]
sage: (triangle/2).vertices_matrix()
[ 0 1/2 1/2]
[1/2 0 1/2]
sage: (triangle/2).vertices_matrix(ZZ)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer
Return the volume of the polytope.
OUTPUT:
The volume of the polytope.
EXAMPLES:
sage: polytopes.n_cube(3).volume()
8
sage: (polytopes.n_cube(3)*2).volume()
64
sage: polytopes.twenty_four_cell().volume()
2
sage: polytopes.regular_polygon(5, base_ring=RDF).volume()
2.37764129...
sage: P5 = polytopes.regular_polygon(5, base_ring=QQ)
sage: P5.volume() # rational approximation
3387471714099766473500515673753476175274812279494567801326487870013/1424719417220622426561086640229666223984528142237277803327699435400
sage: _.n()
2.37764129...
Volume of the same polytope, using the optional package lrs:
sage: P5.volume(engine='lrs') #optional - lrs
2.37764129...
Test whether X is a Polyhedron.
INPUT:
OUTPUT:
Boolean.
EXAMPLES:
sage: p = polytopes.n_cube(2)
sage: from sage.geometry.polyhedron.base import is_Polyhedron
sage: is_Polyhedron(p)
True
sage: is_Polyhedron(123456)
False