Base class for polyhedra¶

class
sage.geometry.polyhedron.base.
Polyhedron_base
(parent, Vrep, Hrep, **kwds)¶ Bases:
sage.structure.element.Element
Base class for Polyhedron objects
INPUT:
parent
– the parent, an instance ofPolyhedra
.Vrep
– a list[vertices, rays, lines]
orNone
. The Vrepresentation of the polyhedron. IfNone
, the polyhedron is determined by the Hrepresentation.Hrep
– a list[ieqs, eqns]
orNone
. The Hrepresentation of the polyhedron. IfNone
, the polyhedron is determined by the Vrepresentation.
Only one of
Vrep
orHrep
can be different fromNone
.
Hrep_generator
()¶ Return an iterator over the objects of the Hrepresentation (inequalities or equations).
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: next(p.Hrep_generator()) An inequality (0, 0, 1) x + 1 >= 0

Hrepresentation
(index=None)¶ Return the objects of the Hrepresentation. Each entry is either an inequality or a equation.
INPUT:
index
– either an integer orNone
.
OUTPUT:
The optional argument is an index running from
0
toself.n_Hrepresentation()1
. If present, the Hrepresentation object at the given index will be returned. Without an argument, returns the list of all Hrepresentation objects.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p.Hrepresentation(0) An inequality (0, 0, 1) x + 1 >= 0 sage: p.Hrepresentation(0) == p.Hrepresentation() [0] True

Hrepresentation_space
()¶ Return the linear space containing the Hrepresentation 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

Hrepresentation_str
(separator='\n', latex=False, style='>=', align=None, **kwds)¶ Return a humanreadable string representation of the Hrepresentation of this polyhedron.
INPUT:
separator
– a string. Default is"\n"
.latex
– a boolean. Default isFalse
.style
– either"positive"
(making all coefficients positive) or
"<="
, or">="
. Default is">="
.
align
– a boolean orNone''. Default is ``None
in which casealign
isTrue
ifseparator
is the newline character. If set, then the lines of the output string are aligned by the comparison symbol by padding blanks.
Keyword parameters of
repr_pretty()
are passed on:prefix
– a stringindices
– a tuple or other iterable
OUTPUT:
A string.
EXAMPLES:
sage: P = polytopes.permutahedron(3) sage: print(P.Hrepresentation_str()) x0 + x1 + x2 == 6 x1  x2 >= 5 x2 >= 3 x1 >= 3 x1 >= 1 x1 + x2 >= 3 x2 >= 1 sage: print(P.Hrepresentation_str(style='<=')) x0  x1  x2 == 6 x1 + x2 <= 5 x2 <= 3 x1 <= 3 x1 <= 1 x1  x2 <= 3 x2 <= 1 sage: print(P.Hrepresentation_str(style='positive')) x0 + x1 + x2 == 6 5 >= x1 + x2 3 >= x2 3 >= x1 x1 >= 1 x1 + x2 >= 3 x2 >= 1 sage: print(P.Hrepresentation_str(latex=True)) \begin{array}{rcl} x_{0} + x_{1} + x_{2} & = & 6 \\ x_{1}  x_{2} & \geq & 5 \\ x_{2} & \geq & 3 \\ x_{1} & \geq & 3 \\ x_{1} & \geq & 1 \\ x_{1} + x_{2} & \geq & 3 \\ x_{2} & \geq & 1 \end{array} sage: print(P.Hrepresentation_str(align=False)) x0 + x1 + x2 == 6 x1  x2 >= 5 x2 >= 3 x1 >= 3 x1 >= 1 x1 + x2 >= 3 x2 >= 1 sage: c = polytopes.cube() sage: c.Hrepresentation_str(separator=', ', style='positive') '1 >= x2, 1 >= x1, 1 >= x0, x0 + 1 >= 0, x2 + 1 >= 0, x1 + 1 >= 0'

Minkowski_difference
(other)¶ Deprecated: Use
minkowski_difference()
instead. See trac ticket #23685 for details.

Minkowski_sum
(other)¶ Deprecated: Use
minkowski_sum()
instead. See trac ticket #23685 for details.

Vrep_generator
()¶ Returns an iterator over the objects of the Vrepresentation (vertices, rays, and lines).
EXAMPLES:
sage: p = polytopes.cyclic_polytope(3,4) sage: vg = p.Vrep_generator() sage: next(vg) A vertex at (0, 0, 0) sage: next(vg) A vertex at (1, 1, 1)

Vrepresentation
(index=None)¶ Return the objects of the Vrepresentation. Each entry is either a vertex, a ray, or a line.
See
sage.geometry.polyhedron.constructor
for a definition of vertex/ray/line.INPUT:
index
– either an integer orNone
.
OUTPUT:
The optional argument is an index running from
0
toself.n_Vrepresentation()1
. If present, the Vrepresentation object at the given index will be returned. Without an argument, returns the list of all Vrepresentation objects.EXAMPLES:
sage: p = polytopes.simplex(4, project=True) sage: p.Vrepresentation(0) A vertex at (0.7071067812, 0.4082482905, 0.2886751346, 0.2236067977) sage: p.Vrepresentation(0) == p.Vrepresentation() [0] True

Vrepresentation_space
()¶ 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

adjacency_matrix
()¶ Return the binary matrix of vertex adjacencies.
EXAMPLES:
sage: polytopes.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 Vrepresentation object are adjacent.Two vertices are adjacent if they are the endpoints of an edge, that is, a onedimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two Vrepresentation objects (see
sage.geometry.polyhedron.constructor
) to be adjacent if they together generate a oneface. There are three possible combinations: Two vertices can bound a finitelength edge.
 A vertex and a ray can generate a halfinfinite edge starting at the vertex and with the direction given by the ray.
 A vertex and a line can generate an infinite edge. The position of the vertex on the line is arbitrary in this case, only its transverse position matters. The direction of the edge is given by the line generator.
For example, take the halfplane:
sage: half_plane = Polyhedron(ieqs=[(0,1,0)]) sage: half_plane.Hrepresentation() (An inequality (1, 0) x + 0 >= 0,)
Its (nonunique) Vrepresentation 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 halfspace in 3 dimensions, there is no onedimensional 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("{} {}".format(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 Vrepresentation of the polygon contains vertices and one ray, then each Vrepresentation object is adjacent to two Vrepresentation objects:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)], ....: rays=[(0,1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(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 Vrepresentation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two Vrepresentation 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("{} {}".format(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)

affine_hull
(as_affine_map=False, orthogonal=False, orthonormal=False, extend=False)¶ 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 fulldimensional polyhedron in this subspace. We provide a projection of the ambient space of the polyhedron to Euclidian space of dimension of the polyhedron. Then the image of the polyhedron under this projection (or, depending on the parameter
as_affine_map
, the projection itself) is returned.INPUT:
as_affine_map
(boolean, default = False) – IfFalse
, return a polyhedron. IfTrue
, return the affine transformation, that sends the embedded polytope to a fulldimensional one. It is given as a pair(A, b)
, where A is a linear transformation andb
is a vector, and the affine transformation sendsv
toA(v)+b
.orthogonal
(boolean, default = False) – ifTrue
, provide an orthogonal transformation.orthonormal
(boolean, default = False) – ifTrue
, provide an orthonormal transformation. If the base ring does not provide the neccessary square roots, the extend parameter needs to be set toTrue
.extend
(boolean, default = False) – ifTrue
, allow base ring to be extended if neccessary. This becomes relevant when requiering an orthonormal transformation.
OUTPUT:
A fulldimensional polyhedron or a linear transformation, depending on the parameter
as_affine_map
.EXAMPLES:
sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]); triangle A 2dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices sage: triangle.affine_hull() A 2dimensional 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))
The resulting affine hulls depend on the parameter
orthogonal
andorthonormal
:sage: L = Polyhedron([[1,0],[0,1]]); L A 1dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices sage: A = L.affine_hull(); A A 1dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (1)) sage: A = L.affine_hull(orthogonal=True); A A 1dimensional polyhedron in QQ^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (2)) sage: A = L.affine_hull(orthonormal=True) Traceback (most recent call last): ... ValueError: The base ring needs to be extended; try with "extend=True" sage: A = L.affine_hull(orthonormal=True, extend=True); A A 1dimensional polyhedron in AA^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (1.414213562373095?))
More generally:
sage: S = polytopes.simplex(); S A 3dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices sage: S.vertices() (A vertex at (0, 0, 0, 1), A vertex at (0, 0, 1, 0), A vertex at (0, 1, 0, 0), A vertex at (1, 0, 0, 0)) sage: A = S.affine_hull(); A A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices sage: A.vertices() (A vertex at (0, 0, 0), A vertex at (0, 0, 1), A vertex at (0, 1, 0), A vertex at (1, 0, 0)) sage: A = S.affine_hull(orthogonal=True); A A 3dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices sage: A.vertices() (A vertex at (0, 0, 0), A vertex at (2, 0, 0), A vertex at (1, 3/2, 0), A vertex at (1, 1/2, 4/3)) sage: A = S.affine_hull(orthonormal=True, extend=True); A A 3dimensional polyhedron in AA^3 defined as the convex hull of 4 vertices sage: A.vertices() (A vertex at (0, 0, 0), A vertex at (1.414213562373095?, 0, 0), A vertex at (0.7071067811865475?, 1.224744871391589?, 0), A vertex at (0.7071067811865475?, 0.4082482904638630?, 1.154700538379252?))
More examples with the
orthonormal
parameter:sage: P = polytopes.permutahedron(3); P A 2dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices sage: set([F.as_polyhedron().affine_hull(orthonormal=True, extend=True).volume() for F in P.affine_hull().faces(1)]) == {1, sqrt(AA(2))} True sage: set([F.as_polyhedron().affine_hull(orthonormal=True, extend=True).volume() for F in P.affine_hull(orthonormal=True, extend=True).faces(1)]) == {sqrt(AA(2))} True sage: D = polytopes.dodecahedron() sage: F = D.faces(2)[0].as_polyhedron() sage: F.affine_hull(orthogonal=True) A 2dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2  5)^2 defined as the convex hull of 5 vertices sage: F.affine_hull(orthonormal=True, extend=True) A 2dimensional polyhedron in AA^2 defined as the convex hull of 5 vertices sage: K.<sqrt2> = QuadraticField(2) sage: P = Polyhedron([2*[K.zero()],2*[sqrt2]]) sage: K.<sqrt2> = QuadraticField(2) sage: P = Polyhedron([2*[K.zero()],2*[sqrt2]]); P A 1dimensional polyhedron in (Number Field in sqrt2 with defining polynomial x^2  2)^2 defined as the convex hull of 2 vertices sage: P.vertices() (A vertex at (0, 0), A vertex at (sqrt2, sqrt2)) sage: A = P.affine_hull(orthonormal=True); A A 1dimensional polyhedron in (Number Field in sqrt2 with defining polynomial x^2  2)^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (2)) sage: K.<sqrt3> = QuadraticField(3) sage: P = Polyhedron([2*[K.zero()],2*[sqrt3]]); P A 1dimensional polyhedron in (Number Field in sqrt3 with defining polynomial x^2  3)^2 defined as the convex hull of 2 vertices sage: P.vertices() (A vertex at (0, 0), A vertex at (sqrt3, sqrt3)) sage: A = P.affine_hull(orthonormal=True) Traceback (most recent call last): ... ValueError: The base ring needs to be extended; try with "extend=True" sage: A = P.affine_hull(orthonormal=True, extend=True); A A 1dimensional polyhedron in AA^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (2.449489742783178?)) sage: sqrt(6).n() 2.44948974278318
The affine hull is combinatorially equivalent to the input:
sage: P.is_combinatorially_isomorphic(P.affine_hull()) True sage: P.is_combinatorially_isomorphic(P.affine_hull(orthogonal=True)) True sage: P.is_combinatorially_isomorphic(P.affine_hull(orthonormal=True, extend=True)) True
The
orthonormal=True
parameter preserves volumes; it provides an isometric copy of the polyhedron:sage: Pentagon = polytopes.dodecahedron().faces(2)[0].as_polyhedron() sage: P = Pentagon.affine_hull(orthonormal=True, extend=True) sage: _, c= P.is_inscribed(certificate=True) sage: c (0.4721359549995794?, 0.6498393924658126?) sage: circumradius = (cvector(P.vertices()[0])).norm() sage: p = polytopes.regular_polygon(5) sage: p.volume() 2.377641290737884? sage: P.volume() 1.53406271079097? sage: p.volume()*circumradius^2 1.534062710790965? sage: P.volume() == p.volume()*circumradius^2 True
One can also use
orthogonal
parameter to calculate volumes; in this case we don’t need to switch base rings. One has to divide by the square root of the determinant of the linear part of the affine transformation times its transpose:sage: Pentagon = polytopes.dodecahedron().faces(2)[0].as_polyhedron() sage: Pnormal = Pentagon.affine_hull(orthonormal=True, extend=True) sage: Pgonal = Pentagon.affine_hull(orthogonal=True) sage: A, b = Pentagon.affine_hull(orthogonal=True, as_affine_map=True) sage: Adet = (A.matrix().transpose()*A.matrix()).det() sage: Pnormal.volume() 1.53406271079097? sage: Pgonal.volume()/sqrt(Adet) 80*(55*sqrt(5)  123)/sqrt(6368*sqrt(5) + 14240) sage: Pgonal.volume()/sqrt(Adet).n(digits=20) 1.5340627107909646651 sage: AA(Pgonal.volume()^2) == (Pnormal.volume()^2)*AA(Adet) True
An other example with
as_affine_map=True
:sage: P = polytopes.permutahedron(4) sage: A, b = P.affine_hull(orthonormal=True, as_affine_map=True, extend=True) sage: Q = P.affine_hull(orthonormal=True, extend=True) sage: Q.center() (0.7071067811865475?, 1.224744871391589?, 1.732050807568878?) sage: A(P.center()) + b == Q.center() True
For unbounded, non fulldimensional polyhedra, the
orthogonal=True
andorthonormal=True
is not implemented:sage: P = Polyhedron(ieqs=[[0, 1, 0], [0, 0, 1], [0, 0, 1]]); P A 1dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: P.is_compact() False sage: P.is_full_dimensional() False sage: P.affine_hull(orthogonal=True) Traceback (most recent call last): ... NotImplementedError: "orthogonal=True" and "orthonormal=True" work only for compact polyhedra sage: P.affine_hull(orthonormal=True) Traceback (most recent call last): ... NotImplementedError: "orthogonal=True" and "orthonormal=True" work only for compact polyhedra
Setting
as_affine_map
toTrue
only works in combination withorthogonal
ororthonormal
set toTrue
:sage: S = polytopes.simplex() sage: S.affine_hull(as_affine_map=True) Traceback (most recent call last): ... NotImplementedError: "as_affine_map=True" only works with "orthogonal=True" and "orthonormal=True"
If the polyhedron is fulldimensional, it is returned:
sage: polytopes.cube().affine_hull() A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: polytopes.cube().affine_hull(as_affine_map=True) (Vector space morphism represented by the matrix: [1 0 0] [0 1 0] [0 0 1] Domain: Vector space of dimension 3 over Rational Field Codomain: Vector space of dimension 3 over Rational Field, (0, 0, 0))

ambient_dim
()¶ 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

ambient_space
()¶ 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

backend
()¶ Return the backend used.
OUTPUT:
The name of the backend used for computations. It will be one of the following backends:
ppl
the Parma Polyhedra Librarycdd
CDDnormaliz
normalizpolymake
polymakefield
a generic Sage implementation
EXAMPLES:
sage: triangle = Polyhedron(vertices = [[1, 0], [0, 1], [1, 1]]) sage: triangle.backend() 'ppl' sage: D = polytopes.dodecahedron() sage: D.backend() 'field' sage: P = Polyhedron([[1.23]]) sage: P.backend() 'cdd'

barycentric_subdivision
(subdivision_frac=None)¶ Return the barycentric subdivision of a compact polyhedron.
DEFINITION:
The barycentric subdivision of a compact polyhedron is a standard way to triangulate its faces in such a way that maximal faces correspond to flags of faces of the starting polyhedron (i.e. a maximal chain in the face lattice of the polyhedron). As a simplicial complex, this is known as the order complex of the face lattice of the polyhedron.
REFERENCE:
See Wikipedia article Barycentric_subdivision Section 6.6, Handbook of Convex Geometry, Volume A, edited by P.M. Gruber and J.M. Wills. 1993, NorthHolland Publishing Co..
INPUT:
subdivision_frac
– number. Gives the proportion how far the new vertices are pulled out of the polytope. Default is \(\frac{1}{3}\) and the value should be smaller than \(\frac{1}{2}\). The subdivision is computed on the polar polyhedron.
OUTPUT:
A Polyhedron object, subdivided as described above.
EXAMPLES:
sage: P = polytopes.hypercube(3) sage: P.barycentric_subdivision() A 3dimensional polyhedron in QQ^3 defined as the convex hull of 26 vertices sage: P = Polyhedron(vertices=[[0,0,0],[0,1,0],[1,0,0],[0,0,1]]) sage: P.barycentric_subdivision() A 3dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices sage: P = Polyhedron(vertices=[[0,1,0],[0,0,1],[1,0,0]]) sage: P.barycentric_subdivision() A 2dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices sage: P = polytopes.regular_polygon(4, base_ring=QQ) sage: P.barycentric_subdivision() A 2dimensional polyhedron in QQ^2 defined as the convex hull of 8 vertices

base_extend
(base_ring, backend=None)¶ Return a new polyhedron over a larger base ring.
This method can also be used to change the backend.
INPUT:
base_ring
– the new base ring.backend
– the new backend, seePolyhedron()
. IfNone
(the default), use the same defaulting behavior as described there; it is not attempted to keep the same backend.
OUTPUT:
The same polyhedron, but over a larger base ring and possibly with a changed backend.
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,0), (0,1)], rays=[(1,1)], base_ring=ZZ); P A 2dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices and 1 ray sage: P.base_extend(QQ) A 2dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray sage: P.base_extend(QQ) == P True

base_ring
()¶ Return the base ring.
OUTPUT:
The ring over which the polyhedron is defined. Must be a subring of the reals to define a polyhedron, in particular comparison must be defined. Popular choices are
ZZ
(the ring of integers, lattice polytope),QQ
(exact arithmetic using gmp),RDF
(double precision floatingpoint arithmetic), orAA
(real algebraic field).
EXAMPLES:
sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]]) sage: triangle.base_ring() == ZZ True

bipyramid
()¶ 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 crosspolytopes are crosspolytopes:
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]

bounded_edges
()¶ 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))

bounding_box
(integral=False, integral_hull=False)¶ Return the coordinates of a rectangular box containing the nonempty polytope.
INPUT:
integral
– Boolean (default:False
). Whether to only allow integral coordinates in the bounding box.integral_hull
– Boolean (default:False
). IfTrue
, return a box containing the integral points of the polytope, orNone, None
if it is known that the polytope has no integral points.
OUTPUT:
A pair of tuples
(box_min, box_max)
wherebox_min
are the coordinates of a point bounding the coordinates of the polytope from below andbox_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: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral_hull=True) (None, None) sage: Polyhedron([ (1/3,2/3), (3/3, 4/3) ]).bounding_box(integral_hull=True) ((1, 1), (1, 1)) sage: polytopes.buckyball(exact=False).bounding_box() ((0.8090169944, 0.8090169944, 0.8090169944), (0.8090169944, 0.8090169944, 0.8090169944))

cdd_Hrepresentation
()¶ Write the inequalities/equations data of the polyhedron in cdd’s Hrepresentation format.
See also
write_cdd_Hrepresentation()
– export the polyhedron as a Hrepresentation to a file.OUTPUT: a string
EXAMPLES:
sage: p = polytopes.hypercube(2) sage: print(p.cdd_Hrepresentation()) Hrepresentation begin 4 3 rational 1 1 0 1 0 1 1 1 0 1 0 1 end sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]],base_ring=AA) sage: triangle.base_ring() Algebraic Real Field sage: triangle.cdd_Hrepresentation() Traceback (most recent call last): ... TypeError: The base ring must be ZZ, QQ, or RDF

cdd_Vrepresentation
()¶ Write the vertices/rays/lines data of the polyhedron in cdd’s Vrepresentation format.
See also
write_cdd_Vrepresentation()
– export the polyhedron as a Vrepresentation to a file.OUTPUT: a string
EXAMPLES:
sage: q = Polyhedron(vertices = [[1,1],[0,0],[1,0],[0,1]]) sage: print(q.cdd_Vrepresentation()) Vrepresentation begin 4 3 rational 1 0 0 1 0 1 1 1 0 1 1 1 end

center
()¶ Return the average of the vertices.
See also
OUTPUT:
The center of the polyhedron. All rays and lines are ignored. Raises a
ZeroDivisionError
for the empty polytope.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p = p + vector([1,0,0]) sage: p.center() (1, 0, 0)

change_ring
(base_ring, backend=None)¶ Return the polyhedron obtained by coercing the entries of the vertices/lines/rays of this polyhedron into the given ring.
This method can also be used to change the backend.
INPUT:
base_ring
– the new base ring.backend
– the new backend orNone
(default), seePolyhedron()
. IfNone
(the default), use the same defaulting behavior as described there; it is not attempted to keep the same backend.
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,0), (0,1)], rays=[(1,1)], base_ring=QQ); P A 2dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray sage: P.change_ring(ZZ) A 2dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices and 1 ray sage: P.change_ring(ZZ) == P True sage: P = Polyhedron(vertices=[(1.3,0), (0,2.3)], base_ring=RDF); P.vertices() (A vertex at (1.3, 0.0), A vertex at (0.0, 2.3)) sage: P.change_ring(QQ).vertices() (A vertex at (13/10, 0), A vertex at (0, 23/10)) sage: P == P.change_ring(QQ) True sage: P.change_ring(ZZ) Traceback (most recent call last): ... TypeError: cannot change the base ring to the Integer Ring (cannot coerce 1.3 into the Integer Ring) sage: P = polytopes.regular_polygon(3); P A 2dimensional polyhedron in AA^2 defined as the convex hull of 3 vertices sage: P.vertices() (A vertex at (0.?e16, 1.000000000000000?), A vertex at (0.866025403784439?, 0.500000000000000?), A vertex at (0.866025403784439?, 0.500000000000000?)) sage: P.change_ring(QQ) Traceback (most recent call last): ... TypeError: cannot change the base ring to the Rational Field (cannot coerce 0.866025403784439? into the Rational Field)
Warning
The base ring
RDF
should be used with care. As it is not an exact ring, certain computations may break or silently produce wrong results, for example changing the base ring from an exact ring intoRDF
may cause a loss of data:sage: P = Polyhedron([[2/3,0],[6666666666666667/10^16,0]], base_ring=AA); P A 1dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices sage: P.change_ring(RDF) A 0dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex sage: P == P.change_ring(RDF) False

combinatorial_automorphism_group
(vertex_graph_only=False)¶ Computes the combinatorial automorphism group.
If
vertex_graph_only
isTrue
, the automorphism group of the vertexedge graph of the polyhedron is returned. Otherwise the automorphism group of the vertexfacet graph, which is isomorphic to the automorphism group of the face lattice is returned.INPUT:
vertex_graph_only
– boolean (default:False
); whether to return the automorphism group of the vertex edges graph or of the lattice.
OUTPUT:
A
PermutationGroup
that is isomorphic to the combinatorial automorphism group is returned. if
vertex_graph_only
isTrue
: The automorphism group of the vertexedge graph of the polyhedron  if
vertex_graph_only
isFalse
(default): The automorphism group of the vertexfacet graph of the polyhedron, seevertex_facet_graph()
. This group is isomorphic to the automorphism group of the face lattice of the polyhedron.
NOTE:
Depending onvertex_graph_only
, this method returns groups that are not necessarily isomorphic, see the examples below.EXAMPLES:
sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)]) sage: quadrangle.combinatorial_automorphism_group().is_isomorphic(groups.permutation.Dihedral(4)) True 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(vertex_graph_only=True) Permutation Group with generators [(A vertex at (1,0,0),A vertex at (1,1,0))]
This shows an example of two polytopes whose vertexedge graphs are isomorphic, but their face_lattices are not isomorphic:
sage: Q=Polyhedron([[123984206864/2768850730773, 101701330976/922950243591, 64154618668/2768850730773, 2748446474675/2768850730773], ....: [11083969050/98314591817, 4717557075/98314591817, 32618537490/98314591817, 91960210208/98314591817], ....: [9690950/554883199, 73651220/554883199, 1823050/554883199, 549885101/554883199], [5174928/72012097, 5436288/72012097, 37977984/72012097, 60721345/72012097], ....: [19184/902877, 26136/300959, 21472/902877, 899005/902877], [53511524/1167061933, 88410344/1167061933, 621795064/1167061933, 982203941/1167061933], ....: [4674489456/83665171433, 4026061312/83665171433, 28596876672/83665171433, 78383796375/83665171433], [857794884940/98972360190089, 10910202223200/98972360190089, 2974263671400/98972360190089, 98320463346111/98972360190089]]) sage: C = polytopes.cyclic_polytope(4,8) sage: C.is_combinatorially_isomorphic(Q) False sage: C.combinatorial_automorphism_group(vertex_graph_only=True).is_isomorphic(Q.combinatorial_automorphism_group(vertex_graph_only=True)) True sage: C.combinatorial_automorphism_group(vertex_graph_only=False).is_isomorphic(Q.combinatorial_automorphism_group(vertex_graph_only=False)) False
The automorphism group of the face lattice is isomorphic to the combinatorial automorphism group:
sage: CG = C.face_lattice().hasse_diagram().automorphism_group() sage: C.combinatorial_automorphism_group().is_isomorphic(CG) True sage: QG = Q.face_lattice().hasse_diagram().automorphism_group() sage: Q.combinatorial_automorphism_group().is_isomorphic(QG) True

contains
(point)¶ Test whether the polyhedron contains the given
point
.See also
INPUT:
point
– coordinates of a point (an iterable).
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 ticket #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 0dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex sage: full.contains([]) True sage: full.contains([0]) False

convex_hull
(other)¶ Return the convex hull of the settheoretic union of the two polyhedra.
INPUT:
other
– aPolyhedron
.
OUTPUT:
The convex hull.
EXAMPLES:
sage: a_simplex = polytopes.simplex(3, project=True) 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

dilation
(scalar)¶ Return the dilated (uniformly stretched) polyhedron.
INPUT:
scalar
– A scalar, not necessarily inbase_ring()
.
OUTPUT:
The polyhedron dilated by that scalar, possibly coerced to a bigger base ring.
EXAMPLES:
sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in srange(2,6)]) sage: next(p.vertex_generator()) A vertex at (2, 4, 8) sage: p2 = p.dilation(2) sage: next(p2.vertex_generator()) A vertex at (4, 8, 16) sage: p.dilation(2) == p * 2 True

dim
()¶ Return the dimension of the polyhedron.
OUTPUT:
1 if the polyhedron is empty, otherwise a nonnegative 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 ticket #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

dimension
()¶ Return the dimension of the polyhedron.
OUTPUT:
1 if the polyhedron is empty, otherwise a nonnegative 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 ticket #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

direct_sum
(other)¶ Return the direct sum of
self
andother
.The direct sum of two polyhedron is the subdirect sum of the two, when they have the origin in their interior. To avoid checking if the origin is contained in both, we place the affine subspace containing
other
at the center ofself
.INPUT:
other
– aPolyhedron_base
.
EXAMPLES:
sage: P1 = Polyhedron([[1],[2]], base_ring=ZZ) sage: P2 = Polyhedron([[3],[4]], base_ring=QQ) sage: ds = P1.direct_sum(P2);ds A 2dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: ds.vertices() (A vertex at (1, 0), A vertex at (2, 0), A vertex at (3/2, 1/2), A vertex at (3/2, 1/2))
See also

equation_generator
()¶ 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: next(p3.equation_generator()) An equation (0.0, 0.0, 1.0) x + 0.0 == 0

equations
()¶ 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,)

equations_list
()¶ 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()
orequation_generator()
instead to iterate over the list ofEquation
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]]

f_vector
()¶ Return the fvector.
OUTPUT:
Returns a vector whose
i
th entry is the number ofi
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)

face_fan
()¶ Return the face fan of a compact rational polyhedron.
OUTPUT:
A fan of the ambient space as a
RationalPolyhedralFan
.See also
EXAMPLES:
sage: T = polytopes.cuboctahedron() sage: T.face_fan() Rational polyhedral fan in 3d lattice M
The polytope should contain the origin in the interior:
sage: P = Polyhedron(vertices = [[1/2, 1], [1, 1/2]]) sage: P.face_fan() Traceback (most recent call last): ... ValueError: face fans are defined only for polytopes containing the origin as an interior point! sage: Q = Polyhedron(vertices = [[1, 1/2], [1, 1/2]]) sage: Q.contains([0,0]) True sage: FF = Q.face_fan(); FF Rational polyhedral fan in 2d lattice M
The polytope has to have rational coordinates:
sage: S = polytopes.dodecahedron() sage: S.face_fan() Traceback (most recent call last): ... NotImplementedError: face fan handles only polytopes over the rationals
REFERENCES:
For more information, see Chapter 7 of [Zie2007].

face_lattice
()¶ Return the facelattice poset.
OUTPUT:
A
FinitePoset
. Elements are given asPolyhedronFace
.In the case of a fulldimensional polytope, the faces are pairs (vertices, inequalities) of the spanning vertices and corresponding saturated inequalities. In general, a face is defined by a pair (Vrep. objects, Hrep. objects). The Vrepresentation objects span the face, and the corresponding Hrepresentation objects are those inequalities and equations that are saturated on the face.
The bottommost element of the face lattice is the “empty face”. It contains no Vrepresentation object. All Hrepresentation objects are incident.
The topmost element is the “full face”. It is spanned by all Vrepresentation objects. The incident Hrepresentation objects are all equations and no inequalities.
In the case of a fulldimensional 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 fulldimensional polytope, the basic algorithm is described in
lattice_from_incidences()
. There are three generalizations of [KP2002] necessary to deal with more general polytopes, corresponding to the extra H/Vrepresentation objects: Lines are removed before calling
lattice_from_incidences()
, and then added back to each face Vrepresentation except for the “empty face”.  Equations are removed before calling
lattice_from_incidences()
, and then added back to each face Hrepresentation.  Rays: Consider the half line as an example. The
Vrepresentation objects are a point and a ray, which we can
think of as a point at infinity. However, the point at
infinity has no inequality associated to it, so there is
only one Hrepresentation object alltogether. The face
lattice does not contain the “face at infinity”. This means
that in
lattice_from_incidences()
, one needs to drop faces with Vrepresentations that have no matching Hrepresentation. In addition, one needs to ensure that every nonempty face contains at least one vertex.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: square.face_lattice() Finite lattice containing 10 elements with distinguished linear extension 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 nonempty face in the face lattice:
sage: line = Polyhedron(vertices=[(0,)], lines=[(1,)]) sage: [ fl.dim() for fl in line.face_lattice() ] [1, 1]
 Lines are removed before calling

face_split
(face)¶ Return the face splitting of the face
face
.Splitting a face correspond to the bipyramid (see
bipyramid()
) ofself
where the two new vertices are placed above and below the center offace
instead of the center of the whole polyhedron. The two new vertices are placed in the new dimension at height \(1\) and \(1\).INPUT:
face
– a PolyhedronFace or a Vertex.
EXAMPLES:
sage: pentagon = polytopes.regular_polygon(5) sage: f = pentagon.faces(1)[0] sage: fsplit_pentagon = pentagon.face_split(f) sage: fsplit_pentagon.f_vector() (1, 7, 14, 9, 1)
See also

face_truncation
(face, linear_coefficients=None, cut_frac=None)¶ Return a new polyhedron formed by truncating a face by an hyperplane.
By default, the normal vector of the hyperplane used to truncate the polyhedron is obtained by taking the barycenter vector of the cone corresponding to the truncated face in the normal fan of the polyhedron. It is possible to change the direction using the option
linear_coefficients
.To determine how deep the truncation is done, the method uses the parameter
cut_frac
. By default it is equal to \(\frac{1}{3}\). Once the normal vector of the cutting hyperplane is chosen, the vertices of polyhedron are evaluated according to the corresponding linear function. The parameter \(\frac{1}{3}\) means that the cutting hyperplane is placed \(\frac{1}{3}\) of the way from the vertices of the truncated face to the next evaluated vertex.INPUT:
face
– a PolyhedronFace.linear_coefficients
– tuple of integer. Specifies the coefficient of the normal vector of the cutting hyperplane used to truncate the face. The default direction is determined using the normal fan of the polyhedron.cut_frac
– number between 0 and 1. Determines where the hyperplane cuts the polyhedron. A value close to 0 cuts very close to the face, whereas a value close to 1 cuts very close to the next vertex (according to the normal vector of the cutting hyperplane). Default is \(\frac{1}{3}\).
OUTPUT:
A Polyhedron object, truncated as described above.
EXAMPLES:
sage: Cube = polytopes.hypercube(3) sage: vertex_trunc1 = Cube.face_truncation(Cube.faces(0)[0]) sage: vertex_trunc1.f_vector() (1, 10, 15, 7, 1) sage: vertex_trunc1.faces(2) (<0,1,2,3>, <2,3,4,5>, <1,2,5,6>, <0,1,6,7,8>, <4,5,6,7,9>, <7,8,9>, <0,3,4,8,9>) sage: vertex_trunc1.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), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1/3, 1), A vertex at (1/3, 1, 1), A vertex at (1, 1, 1/3)) sage: vertex_trunc2 = Cube.face_truncation(Cube.faces(0)[0],cut_frac=1/2) sage: vertex_trunc2.f_vector() (1, 10, 15, 7, 1) sage: vertex_trunc2.faces(2) (<0,1,2,3>, <2,3,4,5>, <1,2,5,6>, <0,1,6,7,8>, <4,5,6,7,9>, <7,8,9>, <0,3,4,8,9>) sage: vertex_trunc2.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), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 0, 1), A vertex at (0, 1, 1), A vertex at (1, 1, 0)) sage: vertex_trunc3 = Cube.face_truncation(Cube.faces(0)[0],cut_frac=0.3) sage: vertex_trunc3.vertices() (A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (0.4, 1.0, 1.0), A vertex at (1.0, 0.4, 1.0), A vertex at (1.0, 1.0, 0.4)) sage: edge_trunc = Cube.face_truncation(Cube.faces(1)[0]) sage: edge_trunc.f_vector() (1, 10, 15, 7, 1) sage: edge_trunc.faces(2) (<0,1,2,3>, <1,2,4,5>, <4,5,6,7>, <0,1,5,6,8>, <2,3,4,7,9>, <6,7,8,9>, <0,3,8,9>) sage: face_trunc = Cube.face_truncation(Cube.faces(2)[0]) sage: face_trunc.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), A vertex at (1/3, 1, 1), A vertex at (1/3, 1, 1), A vertex at (1/3, 1, 1), A vertex at (1/3, 1, 1)) sage: face_trunc.face_lattice().is_isomorphic(Cube.face_lattice()) True

faces
(face_dimension)¶ Return the faces of given dimension
INPUT:
face_dimension
– integer. The dimension of the faces whose representation will be returned.
OUTPUT:
A tuple of
PolyhedronFace
. Seeface
for details. The order random but fixed.EXAMPLES:
Here we find the vertex and face indices of the eight threedimensional facets of the fourdimensional hypercube:
sage: p = polytopes.hypercube(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: [get_idx(_) for _ in face.ambient_Hrepresentation()] [4] sage: [get_idx(_) for _ in face.ambient_Vrepresentation()] [0, 1, 2, 3, 4, 5, 6, 7] sage: [ ([get_idx(_) for _ in face.ambient_Vrepresentation()], ....: [get_idx(_) for _ in 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])]

facet_adjacency_matrix
()¶ Return the adjacency matrix for the facets and hyperplanes.
EXAMPLES:
sage: s4 = polytopes.simplex(4, project=True) sage: s4.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]

gale_transform
()¶ 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.

get_integral_point
(index, **kwds)¶ Return the
index
th integral point in this polyhedron.This is equivalent to
sorted(self.integral_points())[index]
. However, so long as self.integral_points_count() does not need to enumerate all integral points, neither does this method. Hence it can be significantly faster. If the polyhedron is not compact, aValueError
is raised.INPUT:
index
– integer. The index of the integral point to be found. If this is not in [0,self.integral_point_count()
), anIndexError
is raised.**kwds
– optional keyword parameters that are passed toself.integral_points_count()
.
ALGORITHM:
The function computes each of the components of the requested point in turn. To compute x_i, the ith component, it bisects the upper and lower bounds on x_i given by the bounding box. At each bisection, it uses
integral_points_count()
to determine on which side of the bisecting hyperplane the requested point lies.See also
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,1),(1,0),(1,1),(0,1)]) sage: P.get_integral_point(1) (0, 0) sage: P.get_integral_point(4) (1, 1) sage: sorted(P.integral_points()) [(1, 1), (0, 0), (0, 1), (1, 0), (1, 1)] sage: P.get_integral_point(5) Traceback (most recent call last): ... IndexError: ... sage: Q = Polyhedron([(1,3), (2, 7), (9, 77)]) sage: [Q.get_integral_point(i) for i in range(Q.integral_points_count())] == sorted(Q.integral_points()) True sage: Q.get_integral_point(0, explicit_enumeration_threshold=0, triangulation='cddlib') # optional  latte_int (1, 3) sage: Q.get_integral_point(0, explicit_enumeration_threshold=0, triangulation='cddlib', foo=True) # optional  latte_int Traceback (most recent call last): ... RuntimeError: ... sage: R = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]]) sage: R.get_integral_point(0) Traceback (most recent call last): ... ValueError: ...

graph
()¶ Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.
EXAMPLES:
sage: g3 = polytopes.hypercube(3).vertex_graph(); g3 Graph on 8 vertices sage: g3.automorphism_group().cardinality() 48 sage: s4 = polytopes.simplex(4).vertex_graph(); s4 Graph on 5 vertices sage: s4.is_eulerian() True

hyperplane_arrangement
()¶ Return the hyperplane arrangement defined by the equations and inequalities.
OUTPUT:
A
hyperplane arrangement
consisting of the hyperplanes defined by theHrepresentation()
. If the polytope is fulldimensional, this is the hyperplane arrangement spanned by the facets of the polyhedron.EXAMPLES:
sage: p = polytopes.hypercube(2) sage: p.hyperplane_arrangement() Arrangement <t0 + 1  t1 + 1  t1 + 1  t0 + 1>

incidence_matrix
()¶ Return the incidence matrix.
Note
The columns correspond to inequalities/equations in the order
Hrepresentation()
, the rows correspond to vertices/rays/lines in the orderVrepresentation()
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, 1, 0) sage: h = p.Hrepresentation(2) sage: h An inequality (1, 1, 1) x + 2 >= 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

inequalities
()¶ 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]

inequalities_list
()¶ Return a list of inequalities as coefficient lists.
Note
It is recommended to use
inequalities()
orinequality_generator()
instead to iterate over the list ofInequality
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

inequality_generator
()¶ 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]]

integral_points
(threshold=100000)¶ Return the integral points in the polyhedron.
Uses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.
INPUT:
threshold
– integer (default: 100000). Use the naive algorithm as long as the bounding box is smaller than this.
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 fulldimensional:
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 4dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices sage: len(simplex.integral_points()) 49
A case where rounding in the right direction goes a long way:
sage: P = 1/10*polytopes.hypercube(14) sage: P.integral_points() ((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
Finally, the 3d 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() # 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

integral_points_count
(**kwds)¶ Return the number of integral points in the polyhedron.
This generic version of this method simply calls
integral_points
.EXAMPLES:
sage: P = polytopes.cube() sage: P.integral_points_count() 27
We shrink the polyhedron a little bit:
sage: Q = P*(8/9) sage: Q.integral_points_count() 1
Same for a polyhedron whose coordinates are not rationals. Note that the answer is an integer even though there are no guarantees for exactness:
sage: Q = P*RDF(8/9) sage: Q.integral_points_count() 1
Unbounded polyhedra (with or without lattice points) are not supported:
sage: P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]]) sage: P.integral_points_count() Traceback (most recent call last): ... NotImplementedError: ... sage: P = Polyhedron(vertices=[[1, 1]], rays=[[1, 1]]) sage: P.integral_points_count() Traceback (most recent call last): ... NotImplementedError: ...

integrate
(polynomial, **kwds)¶ Return the integral of a polynomial over a polytope.
INPUT:
P
– Polyhedron.polynomial
– A multivariate polynomial or a valid LattE description string for polynomials.**kwds
– additional keyword arguments that are passed to the engine.
OUTPUT:
The integral of the polynomial over the polytope.
Note
The polytope triangulation algorithm is used. This function depends on LattE (i.e., the
latte_int
optional package).EXAMPLES:
sage: P = polytopes.cube() sage: x, y, z = polygens(QQ, 'x, y, z') sage: P.integrate(x^2*y^2*z^2) # optional  latte_int 8/27
If the polyhedron has floating point coordinates, an inexact result can be obtained if we transform to rational coordinates:
sage: P = 1.4142*polytopes.cube() sage: P_QQ = Polyhedron(vertices = [[QQ(vi) for vi in v] for v in P.vertex_generator()]) sage: RDF(P_QQ.integrate(x^2*y^2*z^2)) # optional  latte_int 6.703841212195228
Integral over a non fulldimensional polytope:
sage: x, y = polygens(QQ, 'x, y') sage: P = Polyhedron(vertices=[[0,0],[1,1]]) sage: P.integrate(x*y) # optional  latte_int Traceback (most recent call last): ... NotImplementedError: The polytope must be fulldimensional.

interior_contains
(point)¶ Test whether the interior of the polyhedron contains the given
point
.See also
INPUT:
point
– coordinates of a point.
OUTPUT:
True
orFalse
.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 ticket #10238:
sage: empty = Polyhedron(); empty The empty polyhedron in ZZ^0 sage: empty.interior_contains([]) False

intersection
(other)¶ Return the intersection of one polyhedron with another.
INPUT:
other
– aPolyhedron
.
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.hypercube(3) sage: oct = polytopes.cross_polytope(3) sage: cube.intersection(oct*2) A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
As a shorthand, one may use:
sage: cube & oct*2 A 3dimensional 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 1dimensional 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 0dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex sage: _.Vrepresentation() (A vertex at (1/2, 1/2),)

is_Minkowski_summand
(*args, **kwds)¶ Deprecated: Use
is_minkowski_summand()
instead. See trac ticket #23685 for details.

is_combinatorially_isomorphic
(other, algorithm='bipartite_graph')¶ Return whether the polyhedron is combinatorially isomorphic to another polyhedron.
We only consider bounded polyhedra. By definition, they are combinatorially isomorphic if their faces lattices are isomorphic.
INPUT:
other
– a polyhedron object.algorithm
(default =bipartite_graph
) – the algorithm to use. The other possible value isface_lattice
.
OUTPUT:
True
if the two polyhedra are combinatorially isomorphicFalse
otherwise
REFERENCES:
For the equivalence of the two algorithms see [KK1995], p. 877878
EXAMPLES:
The square is combinatorially isomorphic to the 2dimensional cube:
sage: polytopes.hypercube(2).is_combinatorially_isomorphic(polytopes.regular_polygon(4)) True
All the faces of the 3dimensional permutahedron are either combinatorially isomorphic to a square or a hexagon:
sage: H = polytopes.regular_polygon(6) sage: S = polytopes.hypercube(2) sage: P = polytopes.permutahedron(4) sage: all(F.as_polyhedron().is_combinatorially_isomorphic(S) or F.as_polyhedron().is_combinatorially_isomorphic(H) for F in P.faces(2)) True
Checking that a regular simplex intersected with its reflection through the origin is combinatorially isomorphic to the intersection of a cube with a hyperplane perpendicular to its long diagonal:
sage: def simplex_intersection(k): ....: S1 = Polyhedron([vector(v)vector(polytopes.simplex(k).center()) for v in polytopes.simplex(k).vertices_list()]) ....: S2 = Polyhedron([vector(v) for v in S1.vertices_list()]) ....: return S1.intersection(S2) sage: def cube_intersection(k): ....: C = polytopes.hypercube(k+1) ....: H = Polyhedron(eqns=[[0]+[1 for i in range(k+1)]]) ....: return C.intersection(H) sage: [simplex_intersection(k).is_combinatorially_isomorphic(cube_intersection(k)) for k in range(2,5)] [True, True, True] sage: simplex_intersection(2).is_combinatorially_isomorphic(polytopes.regular_polygon(6)) True sage: simplex_intersection(3).is_combinatorially_isomorphic(polytopes.octahedron()) True
Two polytopes with the same \(f\)vector, but different combinatorial types:
sage: P = Polyhedron([[605520/1525633, 605520/1525633, 1261500/1525633, 52200/1525633, 11833/1525633],\ [720/1769, 600/1769, 1500/1769, 0, 31/1769], [216/749, 240/749, 240/749, 432/749, 461/749], \ [50/181, 50/181, 60/181, 100/181, 119/181], [32/51, 16/51, 4/51, 12/17, 1/17],\ [1, 0, 0, 0, 0], [16/129, 128/129, 0, 0, 1/129], [64/267, 128/267, 24/89, 128/267, 57/89],\ [1200/3953, 1200/3953, 1440/3953, 360/3953, 3247/3953], [1512/5597, 1512/5597, 588/5597, 4704/5597, 2069/5597]]) sage: C = polytopes.cyclic_polytope(5,10) sage: C.f_vector() == P.f_vector(); C.f_vector() True (1, 10, 45, 100, 105, 42, 1) sage: C.is_combinatorially_isomorphic(P) False sage: S = polytopes.simplex(3) sage: S = S.face_truncation(S.faces(0)[0]) sage: S = S.face_truncation(S.faces(0)[0]) sage: S = S.face_truncation(S.faces(0)[0]) sage: T = polytopes.simplex(3) sage: T = T.face_truncation(T.faces(0)[0]) sage: T = T.face_truncation(T.faces(0)[0]) sage: T = T.face_truncation(T.faces(0)[1]) sage: T.is_combinatorially_isomorphic(S) False sage: T.f_vector(), S.f_vector() ((1, 10, 15, 7, 1), (1, 10, 15, 7, 1)) sage: C = polytopes.hypercube(5) sage: C.is_combinatorially_isomorphic(C) True sage: C.is_combinatorially_isomorphic(C, algorithm='magic') Traceback (most recent call last): ... AssertionError: `algorithm` must be 'bipartite graph' or 'face_lattice' sage: G = Graph() sage: C.is_combinatorially_isomorphic(G) Traceback (most recent call last): ... AssertionError: input `other` must be a polyhedron sage: H = Polyhedron(eqns=[[0,1,1,1,1]]); H A 3dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex and 3 lines sage: C.is_combinatorially_isomorphic(H) Traceback (most recent call last): ... AssertionError: polyhedron `other` must be bounded

is_compact
()¶ 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

is_empty
()¶ 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 2dimensional 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 2dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines sage: R.is_empty(), R.is_universe() (False, True)

is_full_dimensional
()¶ Return whether the polyhedron is full dimensional.
OUTPUT:
Boolean. Whether the polyhedron is not contained in any strict affine subspace.
EXAMPLES:
sage: polytopes.hypercube(3).is_full_dimensional() True sage: Polyhedron(vertices=[(1,2,3)], rays=[(1,0,0)]).is_full_dimensional() False

is_inscribed
(certificate=False)¶ This function tests whether the vertices of the polyhedron are inscribed on a sphere.
The polyhedron is expected to be compact and fulldimensional. A fulldimensional compact polytope is inscribed if there exists a point in space which is equidistant to all its vertices.
ALGORITHM:
The function first computes the circumsphere of a fulldimensional simplex with vertices of
self
. It is found by lifting the points on a paraboloid to find the hyperplane on which the circumsphere is lifted. Then, it checks if all other vertices are equidistant to the circumcenter of that simplex.INPUT:
certificate
– (default:False
) boolean; specifies whether to return the circumcenter, if found
OUTPUT:
If
certificate
is true, returns a tuple containing: Boolean.
 The circumcenter of the polytope or None.
If
certificate
is false: a Boolean.
EXAMPLES:
sage: q = Polyhedron(vertices = [[1,1,1,1],[1,1,1,1],[1,1,1,1], ....: [1,1,1,1],[1,1,1,1],[1,1,1,1], ....: [1,1,1,1],[1,1,1,1],[0,0,10/13,24/13], ....: [0,0,10/13,24/13]]) sage: q.is_inscribed(certificate=True) (True, (0, 0, 0, 0)) sage: cube = polytopes.cube() sage: cube.is_inscribed() True sage: translated_cube = Polyhedron(vertices=[v.vector() + vector([1,2,3]) ....: for v in cube.vertices()]) sage: translated_cube.is_inscribed(certificate=True) (True, (1, 2, 3)) sage: truncated_cube = cube.face_truncation(cube.faces(0)[0]) sage: truncated_cube.is_inscribed() False
The method is not implemented for nonfulldimensional polytope or unbounded polyhedra:
sage: square = Polyhedron(vertices=[[1,0,0],[0,1,0],[1,1,0],[0,0,0]]) sage: square.is_inscribed() Traceback (most recent call last): ... NotImplementedError: This function is implemented for fulldimensional polyhedron only. sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)]) sage: p.is_inscribed() Traceback (most recent call last): ... NotImplementedError: This function is not implemented for unbounded polyhedron.

is_lattice_polytope
()¶ 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

is_minkowski_summand
(Y)¶ 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.hypercube(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

is_neighborly
(k=None)¶ Return whether the polyhedron is neighborly.
If the input
k
is provided then return whether the polyhedron isk
neighborlySee Wikipedia article Neighborly_polytope
INPUT:
k
– the dimension up to which to check if every set ofk
vertices forms a face. If nok
is provided, check up to floor of half the dimension of the polyhedron.
OUTPUT:
True
if the every set of up tok
vertices forms a face,False
otherwise
See also
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: cube.is_neighborly() True sage: cube = polytopes.hypercube(4) sage: cube.is_neighborly() False
Cyclic polytopes are neighborly:
sage: all([polytopes.cyclic_polytope(i, i + 1 + j).is_neighborly() for i in range(5) for j in range(3)]) True
The neighborliness of a polyhedron equals floor of dimension half (or larger in case of a simplex) if and only if the polyhedron is neighborly:
sage: testpolys = [polytopes.cube(), polytopes.cyclic_polytope(6, 9), polytopes.simplex(6)] sage: [(P.neighborliness()>=floor(P.dim()/2)) == P.is_neighborly() for P in testpolys] [True, True, True]

is_simple
()¶ 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

is_simplex
()¶ Return whether the polyhedron is a simplex.
EXAMPLES:
sage: Polyhedron([(0,0,0), (1,0,0), (0,1,0)]).is_simplex() True sage: polytopes.simplex(3).is_simplex() True sage: polytopes.hypercube(3).is_simplex() False

is_simplicial
()¶ 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.hypercube(3) sage: p.is_simplicial() False sage: q = polytopes.simplex(5, project=True) 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.

is_universe
()¶ 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 2dimensional 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 2dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines sage: R.is_empty(), R.is_universe() (False, True)

join
(other)¶ Return the join of
self
andother
.The join of two polyhedra is obtained by first placing the two objects in two nonintersecting affine subspaces \(V\), and \(W\) whose affine hull is the whole ambient space, and finally by taking the convex hull of their union. The dimension of the join is the sum of the dimensions of the two polyhedron plus 1.
INPUT:
other
– a polyhedron
EXAMPLES:
sage: P1 = Polyhedron([[0],[1]], base_ring=ZZ) sage: P2 = Polyhedron([[0],[1]], base_ring=QQ) sage: P1.join(P2) A 3dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices sage: P1.join(P1) A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices sage: P2.join(P2) A 3dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
An unbounded example:
sage: R1 = Polyhedron(rays=[[1]]) sage: R1.join(R1) A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 2 vertices and 2 rays

lattice_polytope
(envelope=False)¶ Return an encompassing lattice polytope.
INPUT:
envelope
– boolean (default:False
). If the polyhedron has nonintegral vertices, this option decides whether to return a strictly larger lattice polytope or raise aValueError
. This option has no effect if the polyhedron has already integral vertices.
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 nonintegral 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
, aValueError
is raised.ALGORITHM:
For each nonintegral 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 2d reflexive polytope #3 in 2d lattice M sage: lp.vertices() M(1, 0), M( 0, 1), M( 0, 1), M( 1, 0) in 2d lattice M
Here is a polyhedron with nonintegral 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 2d reflexive polytope #5 in 2d lattice M sage: lp.vertices() M(1, 0), M( 0, 1), M( 1, 1), M( 0, 1), M( 1, 0) in 2d lattice M

line_generator
()¶ Return a generator for the lines of the polyhedron.
EXAMPLES:
sage: pr = Polyhedron(rays = [[1,0],[1,0],[0,1]], vertices = [[1,1]]) sage: next(pr.line_generator()).vector() (1, 0)

lines
()¶ 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),)

lines_list
()¶ 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 ofLine
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

minkowski_difference
(other)¶ Return the Minkowski difference.
Minkowski subtraction can equivalently be defined via Minkowski addition (see
minkowski_sum()
) or as settheoretic intersection via\[X \ominus Y = (X^c \oplus Y)^c = \cap_{y\in Y} (Xy)\]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:
 \((X+Y)Y = X\) for any polyhedra \(X\), \(Y\).
 \((XY)+Y \subseteq X\)
 \((XY)+Y = X\) if and only if Y is a Minkowski summand of X.
INPUT:
other
– aPolyhedron_base
.
OUTPUT:
The Minkowski difference of
self
andother
. Also known as Minkowski subtraction ofother
fromself
.EXAMPLES:
sage: X = polytopes.hypercube(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: (XY)+Y < X True
The polyhedra need not be fulldimensional:
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: (X2Y2)+Y2 < X2 True
Minus sign is really an alias for
minkowski_difference()
sage: four_cube = polytopes.hypercube(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 4dimensional 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 4dimensional polyhedron in QQ^4 defined as the convex hull of 5 vertices

minkowski_sum
(other)¶ Return the Minkowski sum.
Minkowski addition of two subsets of a vector space is defined as
\[X \oplus Y = \cup_{y\in Y} (X+y) = \cup_{x\in X, y\in Y} (x+y)\]See
minkowski_difference()
for a partial inverse operation.INPUT:
other
– aPolyhedron_base
.
OUTPUT:
The Minkowski sum of
self
andother
.EXAMPLES:
sage: X = polytopes.hypercube(3) sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1/2), (0,1/2,0), (1/2,0,0)]) sage: X+Y A 3dimensional polyhedron in QQ^3 defined as the convex hull of 13 vertices sage: four_cube = polytopes.hypercube(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 4dimensional 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 4dimensional polyhedron in QQ^4 defined as the convex hull of 12 vertices

n_Hrepresentation
()¶ Return the number of objects that make up the Hrepresentation 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

n_Vrepresentation
()¶ Return the number of objects that make up the Vrepresentation of the polyhedron.
OUTPUT:
Integer.
EXAMPLES:
sage: p = polytopes.simplex(4) sage: p.n_Vrepresentation() 5 sage: p.n_Vrepresentation() == p.n_vertices() + p.n_rays() + p.n_lines() True

n_equations
()¶ 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

n_facets
()¶ 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

n_inequalities
()¶ 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

n_lines
()¶ 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

n_rays
()¶ 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

n_vertices
()¶ 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

neighborliness
()¶ Returns the largest
k
, such that the polyhedron isk
neighborly.In case of the
d
dimensional simplex, it returnsd + 1
.See Wikipedia article Neighborly_polytope
See also
EXAMPLES:
sage: cube = polytopes.cube() sage: cube.neighborliness() 1 sage: P = Polyhedron(); P The empty polyhedron in ZZ^0 sage: P.neighborliness() 0 sage: P = Polyhedron([[0]]); P A 0dimensional polyhedron in ZZ^1 defined as the convex hull of 1 vertex sage: P.neighborliness() 1 sage: S = polytopes.simplex(5); S A 5dimensional polyhedron in ZZ^6 defined as the convex hull of 6 vertices sage: S.neighborliness() 6 sage: C = polytopes.cyclic_polytope(7,10); C A 7dimensional polyhedron in QQ^7 defined as the convex hull of 10 vertices sage: C.neighborliness() 3 sage: C = polytopes.cyclic_polytope(6,11); C A 6dimensional polyhedron in QQ^6 defined as the convex hull of 11 vertices sage: C.neighborliness() 3 sage: [polytopes.cyclic_polytope(5,n).neighborliness() for n in range(6,10)] [6, 2, 2, 2]

normal_fan
()¶ Return the normal fan of a compact fulldimensional rational polyhedron.
OUTPUT:
A complete fan of the ambient space as a
RationalPolyhedralFan
.See also
EXAMPLES:
sage: S = Polyhedron(vertices = [[0, 0], [1, 0], [0, 1]]) sage: S.normal_fan() Rational polyhedral fan in 2d lattice N sage: C = polytopes.hypercube(4) sage: NF = C.normal_fan(); NF Rational polyhedral fan in 4d lattice N
Currently, it is only possible to get the normal fan of a bounded rational polytope:
sage: P = Polyhedron(rays = [[1, 0], [0, 1]]) sage: P.normal_fan() Traceback (most recent call last): ... NotImplementedError: the normal fan is only supported for polytopes (compact polyhedra). sage: Q = Polyhedron(vertices = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]) sage: Q.normal_fan() Traceback (most recent call last): ... ValueError: the normal fan is only defined for fulldimensional polytopes sage: R = Polyhedron(vertices = [[0, 0], [AA(sqrt(2)), 0], [0, AA(sqrt(2))]]) sage: R.normal_fan() Traceback (most recent call last): ... NotImplementedError: normal fan handles only polytopes over the rationals
REFERENCES:
For more information, see Chapter 7 of [Zie2007].

one_point_suspension
(vertex)¶ Return the onepoint suspension of
self
by splitting the vertexvertex
.The resulting polyhedron has one more vertex and its dimension increases by one.
INPUT:
vertex
– a Vertex ofself
.
EXAMPLES:
sage: cube = polytopes.cube() sage: v = cube.vertices()[0] sage: ops_cube = cube.one_point_suspension(v) sage: ops_cube.f_vector() (1, 9, 24, 24, 9, 1) sage: pentagon = polytopes.regular_polygon(5) sage: v = pentagon.vertices()[0] sage: ops_pentagon = pentagon.one_point_suspension(v) sage: ops_pentagon.f_vector() (1, 6, 12, 8, 1)
It works with a polyhedral face as well:
sage: vv = cube.faces(0)[0] sage: ops_cube2 = cube.one_point_suspension(vv) sage: ops_cube == ops_cube2 True
See also

plot
(point=None, line=None, polygon=None, wireframe='blue', fill='green', projection_direction=None, **kwds)¶ Return a graphical representation.
INPUT:
point
,line
,polygon
– Parameters to pass to point (0d), line (1d), and polygon (2d) plot commands. Allowed values are: A Python dictionary to be passed as keywords to the plot commands.
 A string or triple of numbers: The color. This is
equivalent to passing the dictionary
{'color':...}
. False
: Switches off the drawing of the corresponding graphics object
wireframe
,fill
– Similar topoint
,line
, andpolygon
, butfill
is used for the graphics objects in the dimension of the polytope (or of dimension 2 for higher dimensional polytopes) andwireframe
is used for all lowerdimensional graphics objects (default: ‘green’ forfill
and ‘blue’ forwireframe
)projection_direction
– coordinate list/tuple/iterable orNone
(default). The direction to use for theschlegel_projection()
of the polytope. If not specified, no projection is used in dimensions \(< 4\) and parallel projection is used in dimension \(4\).**kwds
– optional keyword parameters that are passed to all graphics objects.
OUTPUT:
A (multipart) graphics object.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: point = Polyhedron([[1,1]]) sage: line = Polyhedron([[1,1],[2,1]]) sage: cube = polytopes.hypercube(3) sage: hypercube = polytopes.hypercube(4)
By default, the wireframe is rendered in blue and the fill in green:
sage: square.plot() Graphics object consisting of 6 graphics primitives sage: point.plot() Graphics object consisting of 1 graphics primitive sage: line.plot() Graphics object consisting of 2 graphics primitives sage: cube.plot() Graphics3d Object sage: hypercube.plot() Graphics3d Object
Draw the lines in red and nothing else:
sage: square.plot(point=False, line='red', polygon=False) Graphics object consisting of 4 graphics primitives sage: point.plot(point=False, line='red', polygon=False) Graphics object consisting of 0 graphics primitives sage: line.plot(point=False, line='red', polygon=False) Graphics object consisting of 1 graphics primitive sage: cube.plot(point=False, line='red', polygon=False) Graphics3d Object sage: hypercube.plot(point=False, line='red', polygon=False) Graphics3d Object
Draw points in red, no lines, and a blue polygon:
sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics object consisting of 2 graphics primitives sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics object consisting of 1 graphics primitive sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics object consisting of 1 graphics primitive sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics3d Object sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) Graphics3d Object
If we instead use the
fill
andwireframe
options, the coloring depends on the dimension of the object:sage: square.plot(fill='green', wireframe='red') Graphics object consisting of 6 graphics primitives sage: point.plot(fill='green', wireframe='red') Graphics object consisting of 1 graphics primitive sage: line.plot(fill='green', wireframe='red') Graphics object consisting of 2 graphics primitives sage: cube.plot(fill='green', wireframe='red') Graphics3d Object sage: hypercube.plot(fill='green', wireframe='red') Graphics3d Object

polar
()¶ 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 3dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices sage: p.polar() A 3dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices sage: cube = polytopes.hypercube(3) sage: octahedron = polytopes.cross_polytope(3) sage: cube_dual = cube.polar() sage: octahedron == cube_dual True

prism
()¶ Return a prism of the original polyhedron.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: cube = square.prism() sage: cube A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: hypercube = cube.prism() sage: hypercube.n_vertices() 16

product
(other)¶ Return the Cartesian product.
INPUT:
other
– aPolyhedron_base
.
OUTPUT:
The Cartesian product of
self
andother
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 2dimensional 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 2dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: P1 * P2 A 2dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: P2 * P2 A 2dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: 2 * P1 A 1dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices sage: P1 * 2.0 A 1dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices

projection
()¶ 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.hypercube(3) sage: proj = p.projection() sage: proj The projection of a polyhedron into 3 dimensions

pyramid
()¶ Returns a polyhedron that is a pyramid over the original.
EXAMPLES:
sage: square = polytopes.hypercube(2); square A 2dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: egyptian_pyramid = square.pyramid(); egyptian_pyramid A 3dimensional polyhedron in QQ^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)

radius
()¶ 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.hypercube(4) sage: p.radius() 2

radius_square
()¶ 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
base_ring()
.EXAMPLES:
sage: p = polytopes.permutahedron(4, project = False) sage: p.radius_square() 5

random_integral_point
(**kwds)¶ Return an integral point in this polyhedron chosen uniformly at random.
INPUT:
**kwds
– optional keyword parameters that are passed toself.get_integral_point()
.
OUTPUT:
The integral point in the polyhedron chosen uniformly at random. If the polyhedron is not compact, a
ValueError
is raised. If the polyhedron does not contain any integral points, anEmptySetError
is raised.See also
EXAMPLES:
sage: P = Polyhedron(vertices=[(1,1),(1,0),(1,1),(0,1)]) sage: P.random_integral_point() # random (0, 0) sage: P.random_integral_point() in P.integral_points() True sage: P.random_integral_point(explicit_enumeration_threshold=0, triangulation='cddlib') # random, optional  latte_int (1, 1) sage: P.random_integral_point(explicit_enumeration_threshold=0, triangulation='cddlib', foo=7) # optional  latte_int Traceback (most recent call last): ... RuntimeError: ... sage: Q = Polyhedron(vertices=[(2, 1/3)], rays=[(1, 2)]) sage: Q.random_integral_point() Traceback (most recent call last): ... ValueError: ... sage: R = Polyhedron(vertices=[(1/2, 0), (1, 1/2), (0, 1/2)]) sage: R.random_integral_point() Traceback (most recent call last): ... EmptySetError: ...

ray_generator
()¶ 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)]

rays
()¶ 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))

rays_list
()¶ Return a list of rays as coefficient lists.
Note
It is recommended to use
rays()
orray_generator()
instead to iterate over the list ofRay
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

relative_interior_contains
(point)¶ Test whether the relative interior of the polyhedron contains the given
point
.See also
INPUT:
point
– coordinates of a point.
OUTPUT:
True
orFalse
.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 ticket #10238:
sage: empty = Polyhedron(); empty The empty polyhedron in ZZ^0 sage: empty.relative_interior_contains([]) False

render_solid
(**kwds)¶ Return a solid rendering of a 2 or 3d polytope.
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p_solid = p.render_solid(opacity = .7) sage: type(p_solid) <type 'sage.plot.plot3d.index_face_set.IndexFaceSet'>

render_wireframe
(**kwds)¶ 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]

repr_pretty_Hrepresentation
(*args, **kwds)¶ Deprecated: Use
Hrepresentation_str()
instead. See trac ticket #24837 for details.

representative_point
()¶ Return a “generic” point.
See also
OUTPUT:
A point as a coordinate vector. The point is chosen to be interior as far as possible. If the polyhedron is not fulldimensional, the point is in the relative interior. If the polyhedron is zerodimensional, 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)

restricted_automorphism_group
(output='abstract')¶ Return the restricted automorphism group.
First, let the linear automorphism group be the subgroup of the affine group \(AGL(d,\RR) = GL(d,\RR) \ltimes \RR^d\) preserving the \(d\)dimensional polyhedron. The affine 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
\[Q = \Big\{ (x,y) \Big x\geq 0,\; y\geq0 \Big\} \subset \QQ^2\]Then the linear automorphism group is
\[\begin{split}\mathrm{Aut}(Q) = \left\{ \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} ,~ \begin{pmatrix} 0 & c \\ d & 0 \end{pmatrix} :~ a, b, c, d \in \QQ_{>0} \right\} \subset GL(2,\QQ) \subset E(d)\end{split}\]Note that there are no translations that map the quadrant \(Q\) to itself, so the linear automorphism group is contained in the general linear group (the subgroup of transformations preserving the origin). The restricted automorphism group is
\[\begin{split}\mathrm{Aut}(Q) = \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} ,~ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \right\} \simeq \ZZ_2\end{split}\]INPUT:
output
– how the group should be represented:"abstract"
(default) – return an abstract permutation group without further meaning."permutation"
– return a permutation group on the indices of the polyhedron generators. For example, the permutation(0,1)
would correspond to swappingself.Vrepresentation(0)
andself.Vrepresentation(1)
."matrix"
– return a matrix group representing affine transformations. When acting on affine vectors, you should append a \(1\) to every vector. If the polyhedron is not full dimensional, the returned matrices act as the identity on the orthogonal complement of the affine space spanned by the polyhedron."matrixlist"
– likematrix
, but return the list of elements of the matrix group. Useful for fields without a good implementation of matrix groups or to avoid the overhead of creating the group.
OUTPUT:
 For
output="abstract"
andoutput="permutation"
: aPermutationGroup
.  For
output="matrix"
: aMatrixGroup
.  For
output="matrixlist"
: a list of matrices.
REFERENCES:
EXAMPLES:
A crosspolytope example:
sage: P = polytopes.cross_polytope(3) sage: P.restricted_automorphism_group() == PermutationGroup([[(3,4)], [(2,3),(4,5)],[(2,5)],[(1,2),(5,6)],[(1,6)]]) True sage: P.restricted_automorphism_group(output="permutation") == PermutationGroup([[(2,3)],[(1,2),(3,4)],[(1,4)],[(0,1),(4,5)],[(0,5)]]) True sage: mgens = [[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], [[1,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,1]], [[0,1,0,0],[1,0,0,0],[0,0,1,0],[0,0,0,1]]]
We test groups for equality in a foolproof way; they can have different generators, etc:
sage: poly_g = P.restricted_automorphism_group(output="matrix") sage: matrix_g = MatrixGroup([matrix(QQ,t) for t in mgens]) sage: all(t.matrix() in poly_g for t in matrix_g.gens()) True sage: all(t.matrix() in matrix_g for t in poly_g.gens()) True
24cell example:
sage: P24 = polytopes.twenty_four_cell() sage: AutP24 = P24.restricted_automorphism_group() sage: PermutationGroup([ ....: '(1,20,2,24,5,23)(3,18,10,19,4,14)(6,21,11,22,7,15)(8,12,16,17,13,9)', ....: '(1,21,8,24,4,17)(2,11,6,15,9,13)(3,20)(5,22)(10,16,12,23,14,19)' ....: ]).is_isomorphic(AutP24) True sage: AutP24.order() 1152
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(output="permutation") Permutation Group with generators [(1,2)]
Also, the polyhedron need not be fulldimensional:
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)] sage: G = P.restricted_automorphism_group(output="matrixlist") sage: G [ [1 0 0 0 0 0] [ 87/55 82/55 2/5 38/55 98/55 12/11] [0 1 0 0 0 0] [142/55 27/55 2/5 38/55 98/55 12/11] [0 0 1 0 0 0] [142/55 82/55 3/5 38/55 98/55 12/11] [0 0 0 1 0 0] [142/55 82/55 2/5 93/55 98/55 12/11] [0 0 0 0 1 0] [142/55 82/55 2/5 38/55 153/55 12/11] [0 0 0 0 0 1], [ 0 0 0 0 0 1] ] sage: g = AffineGroup(5, QQ)(G[1]) sage: g [ 87/55 82/55 2/5 38/55 98/55] [12/11] [142/55 27/55 2/5 38/55 98/55] [12/11] x > [142/55 82/55 3/5 38/55 98/55] x + [12/11] [142/55 82/55 2/5 93/55 98/55] [12/11] [142/55 82/55 2/5 38/55 153/55] [12/11] sage: g^2 [1 0 0 0 0] [0] [0 1 0 0 0] [0] x > [0 0 1 0 0] x + [0] [0 0 0 1 0] [0] [0 0 0 0 1] [0] sage: g(list(P.vertices()[0])) (7, 8, 9, 10, 11) sage: g(list(P.vertices()[1])) (1, 2, 3, 4, 5)
Affine transformations do not change the restricted automorphism group. For example, any nondegenerate 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)]
The
output="matrixlist"
can be used over fields without a complete implementation of matrix groups:sage: P = polytopes.dodecahedron(); P A 3dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2  5)^3 defined as the convex hull of 20 vertices sage: G = P.restricted_automorphism_group(output="matrixlist") sage: len(G) 120
Floatingpoint computations are supported with a simple fuzzy zero implementation:
sage: P = Polyhedron(vertices=[(1/3,0,0,1),(0,1/4,0,1),(0,0,1/5,1)], base_ring=RDF) sage: P.restricted_automorphism_group() Permutation Group with generators [(2,3), (1,2)] sage: len(P.restricted_automorphism_group(output="matrixlist")) 6

schlegel_projection
(projection_dir=None, height=1.1)¶ Return the Schlegel projection.
 The polyhedron is translated such that its
center()
is at the origin.  The vertices are then normalized to the unit sphere
 The normalized points are stereographically projected from a point slightly outside of the sphere.
INPUT:
projection_direction
– coordinate list/tuple/iterable orNone
(default). The direction of the Schlegel projection. For a fulldimensional polyhedron, the default is the first facet normal; Otherwise, the vector consisting of the first n primes is chosen.height
– float (default: \(1.1\)). How far outside of the unit sphere the focal point is.
OUTPUT:
A
Projection
object.EXAMPLES:
sage: p = polytopes.hypercube(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
 The polyhedron is translated such that its

show
(**kwds)¶ Display graphics immediately
This method attempts to display the graphics immediately, without waiting for the currently running code (if any) to return to the command line. Be careful, calling it from within a loop will potentially launch a large number of external viewer programs.
INPUT:
kwds
– optional keyword arguments. Seeplot()
for the description of available options.
OUTPUT:
This method does not return anything. Use
plot()
if you want to generate a graphics object that can be saved or further transformed.EXAMPLES:
sage: square = polytopes.hypercube(2) sage: square.show(point='red')

stack
(face, position=None)¶ Return a new polyhedron formed by stacking onto a
face
. Stacking a face adds a new vertex located slightly outside of the designated face.INPUT:
face
– a PolyhedronFace.position
– a positive integer. Determines a relative distance from the barycenter offace
. A value close to 0 will place the new vertex close to the face and a large value further away. Default is \(1\). If the given value is too large, an error is returned.
OUTPUT:
A Polyhedron object
EXAMPLES:
sage: cube = polytopes.cube() sage: square_face = cube.faces(2)[2] sage: stacked_square = cube.stack(square_face) sage: stacked_square.f_vector() (1, 9, 16, 9, 1) sage: edge_face = cube.faces(1)[3] sage: stacked_edge = cube.stack(edge_face) sage: stacked_edge.f_vector() (1, 9, 17, 10, 1) sage: cube.stack(cube.faces(0)[0]) Traceback (most recent call last): ... ValueError: Can not stack onto a vertex. sage: stacked_square_half = cube.stack(square_face,position=1/2) sage: stacked_square_half.f_vector() (1, 9, 16, 9, 1) sage: stacked_square_large = cube.stack(square_face,position=10) sage: hexaprism = polytopes.regular_polygon(6).prism() sage: hexaprism.f_vector() (1, 12, 18, 8, 1) sage: square_face = hexaprism.faces(2)[0] sage: stacked_hexaprism = hexaprism.stack(square_face) sage: stacked_hexaprism.f_vector() (1, 13, 22, 11, 1) sage: hexaprism.stack(square_face,position=4) Traceback (most recent call last): ... ValueError: The chosen position is too large.
It is possible to stack on unbounded faces:
sage: Q = Polyhedron(vertices=[[0,1],[1,0]],rays=[[1,1]]) sage: E = Q.faces(1) sage: Q.stack(E[0],1/2).Vrepresentation() (A vertex at (0, 1), A vertex at (0, 2), A vertex at (1, 0), A ray in the direction (1, 1)) sage: Q.stack(E[1],1/2).Vrepresentation() (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A ray in the direction (1, 1)) sage: Q.stack(E[2],1/2).Vrepresentation() (A vertex at (0, 1), A vertex at (1, 0), A ray in the direction (1, 1), A vertex at (2, 0))

subdirect_sum
(other)¶ Return the subdirect sum of
self
andother
.The subdirect sum of two polyhedron is a projection of the join of the two polytopes. It is obtained by placing the two objects in orthogonal subspaces intersecting at the origin.
INPUT:
other
– aPolyhedron_base
.
EXAMPLES:
sage: P1 = Polyhedron([[1],[2]], base_ring=ZZ) sage: P2 = Polyhedron([[3],[4]], base_ring=QQ) sage: sds = P1.subdirect_sum(P2);sds A 2dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: sds.vertices() (A vertex at (0, 3), A vertex at (0, 4), A vertex at (1, 0), A vertex at (2, 0))
See also

to_linear_program
(solver=None, return_variable=False, base_ring=None)¶ Return a linear optimization problem over the polyhedron in the form of a
MixedIntegerLinearProgram
.INPUT:
solver
– select a solver (MIP backend). See the documentation of forMixedIntegerLinearProgram
. Set toNone
by default.return_variable
– (default:False
) IfTrue
, return a tuple(p, x)
, wherep
is theMixedIntegerLinearProgram
object andx
is the vectorvalued MIP variable in this problem, indexed from 0. IfFalse
, only returnp
.base_ring
– select a field over which the linear program should be set up. UseRDF
to request a fast inexact (floating point) solver even ifself
is exact.
Note that the
MixedIntegerLinearProgram
object will have the null function as an objective to be maximized.See also
polyhedron()
– return the polyhedron associated with aMixedIntegerLinearProgram
object.EXAMPLES:
Exact rational linear program:
sage: p = polytopes.cube() sage: p.to_linear_program() Linear Program (no objective, 3 variables, 6 constraints) sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(2*x[0] + 1*x[1] + 39*x[2]) sage: lp.solve() 42 sage: lp.get_values(x[0], x[1], x[2]) [1, 1, 1]
Floatingpoint linear program:
sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF) sage: lp.set_objective(2*x[0] + 1*x[1] + 39*x[2]) sage: lp.solve() 42.0
Irrational algebraic linear program over an embedded number field:
sage: p=polytopes.icosahedron() sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() 1/4*sqrt5 + 3/4
Same example with floating point:
sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # tol 1e5 1.3090169943749475
Same example with a specific floating point solver:
sage: lp, x = p.to_linear_program(return_variable=True, solver='GLPK') sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # tol 1e8 1.3090169943749475
Irrational algebraic linear program over \(AA\):
sage: p=polytopes.icosahedron(base_ring=AA) sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # long time 1.309016994374948?

translation
(displacement)¶ Return the translated polyhedron.
INPUT:
displacement
– a displacement vector or a list/tuple of coordinates that determines a displacement vector.
OUTPUT:
The translated polyhedron.
EXAMPLES:
sage: P = Polyhedron([[0,0],[1,0],[0,1]], base_ring=ZZ) sage: P.translation([2,1]) A 2dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: P.translation( vector(QQ,[2,1]) ) A 2dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices

triangulate
(engine='auto', connected=True, fine=False, regular=None, star=None)¶ Returns a triangulation of the polytope.
INPUT:
engine
– either ‘auto’ (default), ‘internal’, or ‘TOPCOM’. The latter two instruct this package to always use its own triangulation algorithms or TOPCOM’s algorithms, respectively. By default (‘auto’), TOPCOM is used if it is available and internal routines otherwise.
The remaining keyword parameters are passed through to the
PointConfiguration
constructor: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 orNone
(default:None
). Whether the triangulations must be regular. A regular triangulation is one that is induced by a piecewiselinear convex support function. In other words, the shadows of the faces of a polyhedron in one higher dimension.True
: Only regular triangulations.False
: Only nonregular triangulations.None
(default): Both kinds of triangulation.
star
– eitherNone
(default) 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.)
OUTPUT:
A triangulation of the convex hull of the vertices as a
Triangulation
. The indices in the triangulation correspond to theVrepresentation()
objects.EXAMPLES:
sage: cube = polytopes.hypercube(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 3dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices

truncation
(cut_frac=None)¶ Return a new polyhedron formed from two points on each edge between two vertices.
INPUT:
cut_frac
– integer, how deeply to cut into the edge. Default is \(\frac{1}{3}\).
OUTPUT:
A Polyhedron object, truncated as described above.
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: trunc_cube = cube.truncation() sage: trunc_cube.n_vertices() 24 sage: trunc_cube.n_inequalities() 14

vertex_adjacency_matrix
()¶ Return the binary matrix of vertex adjacencies.
EXAMPLES:
sage: polytopes.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 Vrepresentation object are adjacent.Two vertices are adjacent if they are the endpoints of an edge, that is, a onedimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two Vrepresentation objects (see
sage.geometry.polyhedron.constructor
) to be adjacent if they together generate a oneface. There are three possible combinations: Two vertices can bound a finitelength edge.
 A vertex and a ray can generate a halfinfinite edge starting at the vertex and with the direction given by the ray.
 A vertex and a line can generate an infinite edge. The position of the vertex on the line is arbitrary in this case, only its transverse position matters. The direction of the edge is given by the line generator.
For example, take the halfplane:
sage: half_plane = Polyhedron(ieqs=[(0,1,0)]) sage: half_plane.Hrepresentation() (An inequality (1, 0) x + 0 >= 0,)
Its (nonunique) Vrepresentation 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 halfspace in 3 dimensions, there is no onedimensional 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("{} {}".format(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 Vrepresentation of the polygon contains vertices and one ray, then each Vrepresentation object is adjacent to two Vrepresentation objects:
sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)], ....: rays=[(0,1)]) sage: for v in P.Vrep_generator(): ....: print("{} {}".format(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 Vrepresentation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two Vrepresentation 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("{} {}".format(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)

vertex_digraph
(f, increasing=True)¶ Return the directed graph of the polyhedron according to a linear form.
The underlying undirected graph is the graph of vertices and edges.
INPUT:
f
– a linear form. The linear form can be provided as: a vector space morphism with onedimensional codomain, (see
sage.modules.vector_space_morphism.linear_transformation()
andsage.modules.vector_space_morphism.VectorSpaceMorphism
)  a vector ; in this case the linear form is obtained by duality
using the dot product:
f(v) = v.dot_product(f)
.
 a vector space morphism with onedimensional codomain, (see
increasing
– boolean (defaultTrue
) whether to orient edges in the increasing or decreasing direction.
By default, an edge is oriented from \(v\) to \(w\) if \(f(v) \leq f(w)\).
If \(f(v)=f(w)\), then two opposite edges are created.
EXAMPLES:
sage: penta = Polyhedron([[0,0],[1,0],[0,1],[1,2],[3,2]]) sage: G = penta.vertex_digraph(vector([1,1])); G Digraph on 5 vertices sage: G.sinks() [A vertex at (3, 2)] sage: A = matrix(ZZ, [[1], [1]]) sage: f = linear_transformation(A) sage: G = penta.vertex_digraph(f) ; G Digraph on 5 vertices sage: G.is_directed_acyclic() False
See also

vertex_facet_graph
(labels=True)¶ Return the vertexfacet graph.
This function constructs a directed bipartite graph. The nodes of the graph correspond to the vertices of the polyhedron and the facets of the polyhedron. There is an directed edge from a vertex to a face if and only if the vertex is incident to the face.
INPUT:
labels
– boolean (default:True
); decide how the nodes of the graph are labelled. Either with the original vertices/facets of the Polyhedron or with integers.
OUTPUT:
 a bipartite DiGraph. If
labels
isTrue
, then the nodes of the graph will actually be the vertices and facets ofself
, otherwise they will be integers.
EXAMPLES:
sage: P = polytopes.cube() sage: G = P.vertex_facet_graph(); G Digraph on 14 vertices sage: G.vertices(key = lambda v: str(v)) [A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), A vertex at (1, 1, 1), An inequality (1, 0, 0) x + 1 >= 0, An inequality (0, 1, 0) x + 1 >= 0, An inequality (0, 0, 1) x + 1 >= 0, An inequality (0, 0, 1) x + 1 >= 0, An inequality (0, 1, 0) x + 1 >= 0, An inequality (1, 0, 0) x + 1 >= 0] sage: G.automorphism_group().is_isomorphic(P.face_lattice().hasse_diagram().automorphism_group()) True sage: O = polytopes.octahedron(); O A 3dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices sage: O.vertex_facet_graph() Digraph on 14 vertices sage: H = O.vertex_facet_graph() sage: G.is_isomorphic(H) False sage: G.reverse_edges(G.edges()) sage: G.is_isomorphic(H) True

vertex_generator
()¶ 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: next(v_gen) # the first vertex A vertex at (0, 1) sage: next(v_gen) # the second vertex A vertex at (1, 0) sage: next(v_gen) # the third vertex A vertex at (1, 1) sage: try: next(v_gen) # there are only three vertices ....: except StopIteration: print("STOP") STOP sage: type(v_gen) <... 'generator'> sage: [ v for v in triangle.vertex_generator() ] [A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1)]

vertex_graph
()¶ Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.
EXAMPLES:
sage: g3 = polytopes.hypercube(3).vertex_graph(); g3 Graph on 8 vertices sage: g3.automorphism_group().cardinality() 48 sage: s4 = polytopes.simplex(4).vertex_graph(); s4 Graph on 5 vertices sage: s4.is_eulerian() True

vertices
()¶ 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))

vertices_list
()¶ Return a list of vertices of the polyhedron.
Note
It is recommended to use
vertex_generator()
instead to iterate over the list ofVertex
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

vertices_matrix
(base_ring=None)¶ Return the coordinates of the vertices as the columns of a matrix.
INPUT:
base_ring
– A ring orNone
(default). The base ring of the returned matrix. If not specified, the base ring of the polyhedron is used.
OUTPUT:
A matrix over
base_ring
whose columns are the coordinates of the vertices. ATypeError
is raised if the coordinates cannot be converted tobase_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

volume
(measure='ambient', engine='auto', **kwds)¶ Return the volume of the polytope.
INPUT:
measure
– string. The measure to use. Allowed values are:ambient
(default): Lebesgue measure of ambient space (volume)induced
: Lebesgue measure of the affine hull (relative volume)induced_rational
: Scaling of the Lebesgue measure for rational polytopes
engine
– string. The backend to use. Allowed values are:'auto'
(default): choose engine according to measure'internal'
: seetriangulate()
.'TOPCOM'
: seetriangulate()
.'lrs'
: use David Avis’s lrs program (optional).'latte'
: use LattE integrale program (optional).
**kwds
– keyword arguments that are passed to the triangulation engine.
OUTPUT:
The volume of the polytope.
EXAMPLES:
sage: polytopes.hypercube(3).volume() 8 sage: (polytopes.hypercube(3)*2).volume() 64 sage: polytopes.twenty_four_cell().volume() 2
Volume of the same polytopes, using the optional package lrslib (which requires a rational polytope). For mysterious historical reasons, Sage casts lrs’s exact answer to a float:
sage: I3 = polytopes.hypercube(3) sage: I3.volume(engine='lrs') #optional  lrslib 8.0 sage: C24 = polytopes.twenty_four_cell() sage: C24.volume(engine='lrs') #optional  lrslib 2.0
If the base ring is exact, the answer is exact:
sage: P5 = polytopes.regular_polygon(5) sage: P5.volume() 2.377641290737884? sage: polytopes.icosahedron().volume() 5/12*sqrt5 + 5/4 sage: numerical_approx(_) # abs tol 1e9 2.18169499062491
When considering lowerdimensional polytopes, we can ask for the ambient (fulldimensional), the induced measure (of the affine hull) or, in the case of lattice polytopes, for the induced rational measure. This is controlled by the parameter \(measure\). Different engines may have different ideas on the definition of volume of a lowerdimensional object:
sage: P = Polyhedron([[0, 0], [1, 1]]) sage: P.volume() 0 sage: P.volume(measure='induced') sqrt(2) sage: P.volume(measure='induced_rational') # optional  latte_int 1 sage: S = polytopes.regular_polygon(6); S A 2dimensional polyhedron in AA^2 defined as the convex hull of 6 vertices sage: edge = S.faces(1)[2].as_polyhedron() sage: edge.vertices() (A vertex at (0.866025403784439?, 1/2), A vertex at (0, 1)) sage: edge.volume() 0 sage: edge.volume(measure='induced') 1 sage: Dexact = polytopes.dodecahedron() sage: v = Dexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal'); v 80*(55*sqrt(5)  123)/sqrt(6368*sqrt(5) + 14240) sage: v = Dexact.faces(2)[4].as_polyhedron().volume(measure='induced', engine='internal'); v 80*(55*sqrt(5)  123)/sqrt(6368*sqrt(5) + 14240) sage: RDF(v) # abs tol 1e9 1.53406271079044 sage: Dinexact = polytopes.dodecahedron(exact=False) sage: w = Dinexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal'); RDF(w) # abs tol 1e9 1.534062710738235 sage: [polytopes.simplex(d).volume(measure='induced') for d in range(1,5)] == [sqrt(d+1)/factorial(d) for d in range(1,5)] True sage: I = Polyhedron([[3, 0], [0, 9]]) sage: I.volume(measure='induced') 3*sqrt(10) sage: I.volume(measure='induced_rational') # optional  latte_int 3 sage: T = Polyhedron([[3, 0, 0], [0, 4, 0], [0, 0, 5]]) sage: T.volume(measure='induced') 1/2*sqrt(769) sage: T.volume(measure='induced_rational') # optional  latte_int 1/2 sage: Q = Polyhedron(vertices=[(0, 0, 1, 1), (0, 1, 1, 0), (1, 1, 0, 0)]) sage: Q.volume(measure='induced') 1 sage: Q.volume(measure='induced_rational') # optional  latte_int 1/2
The volume of a fulldimensional unbounded polyhedron is infinity:
sage: P = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]]) sage: P.volume() +Infinity
The volume of a non fulldimensional unbounded polyhedron depends on the measure used:
sage: P = Polyhedron(ieqs = [[1,1,1],[1,1,1],[3,1,0]]); P A 1dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: P.volume() 0 sage: P.volume(measure='induced') +Infinity sage: P.volume(measure='ambient') 0 sage: P.volume(measure='induced_rational') +Infinity

write_cdd_Hrepresentation
(filename)¶ Export the polyhedron as a Hrepresentation to a file.
INPUT:
filename
– the output file.
See also
cdd_Hrepresentation()
– return the Hrepresentation of the polyhedron as a string.EXAMPLES:
sage: from sage.misc.temporary_file import tmp_filename sage: filename = tmp_filename(ext='.ext') sage: polytopes.cube().write_cdd_Hrepresentation(filename)

write_cdd_Vrepresentation
(filename)¶ Export the polyhedron as a Vrepresentation to a file.
INPUT:
filename
– the output file.
See also
cdd_Vrepresentation()
– return the Vrepresentation of the polyhedron as a string.EXAMPLES:
sage: from sage.misc.temporary_file import tmp_filename sage: filename = tmp_filename(ext='.ext') sage: polytopes.cube().write_cdd_Vrepresentation(filename)

sage.geometry.polyhedron.base.
is_Polyhedron
(X)¶ Test whether
X
is a Polyhedron.INPUT:
X
– anything.
OUTPUT:
Boolean.
EXAMPLES:
sage: p = polytopes.hypercube(2) sage: from sage.geometry.polyhedron.base import is_Polyhedron sage: is_Polyhedron(p) True sage: is_Polyhedron(123456) False