Base class for polyhedra¶

class sage.geometry.polyhedron.base.Polyhedron_base(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)¶

Bases: sage.structure.element.Element, sage.geometry.convex_set.ConvexSet_closed

Base class for Polyhedron objects

INPUT:

parent – the parent, an instance of Polyhedra.
Vrep – a list [vertices, rays, lines] or None. The V-representation of the polyhedron. If None, the polyhedron is determined by the H-representation.
Hrep – a list [ieqs, eqns] or None. The H-representation of the polyhedron. If None, the polyhedron is determined by the V-representation.
Vrep_minimal (optional) – see below
Hrep_minimal (optional) – see below
pref_rep – string (default: None);
one of``Vrep`` or Hrep to pick this in case the backend cannot initialize from complete double description
mutable – ignored

If both Vrep and Hrep are provided, then Vrep_minimal and Hrep_minimal must be set to True.

Hrep_generator()¶

Return an iterator over the objects of the H-representation (inequalities or equations).

EXAMPLES:

sage: p = polytopes.hypercube(3)
sage: next(p.Hrep_generator())
An inequality (-1, 0, 0) x + 1 >= 0

Hrepresentation(index=None)¶

Return the objects of the H-representation. Each entry is either an inequality or a equation.

INPUT:

index – either an integer or None

OUTPUT:

The optional argument is an index running from 0 to self.n_Hrepresentation()-1. If present, the H-representation object at the given index will be returned. Without an argument, returns the list of all H-representation objects.

EXAMPLES:

sage: p = polytopes.hypercube(3, backend='field')
sage: p.Hrepresentation(0)
An inequality (-1, 0, 0) x + 1 >= 0
sage: p.Hrepresentation(0) == p.Hrepresentation()[0]
True

Hrepresentation_space()¶

Return the linear space containing the H-representation vectors.

OUTPUT:

A free module over the base ring of dimension ambient_dim() + 1.

EXAMPLES:

sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.Hrepresentation_space()
Ambient free module of rank 5 over the principal ideal domain Integer Ring

Hrepresentation_str(separator='\\n', latex=False, style='>=', align=None, **kwds)¶

Return a human-readable string representation of the Hrepresentation of this polyhedron.

INPUT:

separator – a string. Default is "\n".
latex – a boolean. Default is False.
style – either "positive" (making all coefficients positive)
or "<=", or ">=". Default is ">=".
align – a boolean or None''. Default is ``None in which case
align is True if separator 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 string
indices – a tuple or other iterable

OUTPUT:

A string.

EXAMPLES:

sage: P = polytopes.permutahedron(3)
sage: print(P.Hrepresentation_str())
x0 + x1 + x2 ==  6
     x0 + x1 >=  3
    -x0 - x1 >= -5
          x1 >=  1
         -x0 >= -3
          x0 >=  1
         -x1 >= -3

sage: print(P.Hrepresentation_str(style='<='))
-x0 - x1 - x2 == -6
     -x0 - x1 <= -3
      x0 + x1 <=  5
          -x1 <= -1
           x0 <=  3
          -x0 <= -1
           x1 <=  3

sage: print(P.Hrepresentation_str(style='positive'))
x0 + x1 + x2 == 6
     x0 + x1 >= 3
           5 >= x0 + x1
          x1 >= 1
           3 >= x0
          x0 >= 1
           3 >= x1

sage: print(P.Hrepresentation_str(latex=True))
\begin{array}{rcl}
x_{0} + x_{1} + x_{2} & =    &  6 \\
        x_{0} + x_{1} & \geq &  3 \\
       -x_{0} - x_{1} & \geq & -5 \\
                x_{1} & \geq &  1 \\
               -x_{0} & \geq & -3 \\
                x_{0} & \geq &  1 \\
               -x_{1} & \geq & -3
\end{array}

sage: print(P.Hrepresentation_str(align=False))
x0 + x1 + x2 == 6
x0 + x1 >= 3
-x0 - x1 >= -5
x1 >= 1
-x0 >= -3
x0 >= 1
-x1 >= -3

sage: c = polytopes.cube()
sage: c.Hrepresentation_str(separator=', ', style='positive')
'1 >= x0, 1 >= x1, 1 >= x2, x0 + 1 >= 0, x2 + 1 >= 0, x1 + 1 >= 0'

Vrep_generator()¶

Return an iterator over the objects of the V-representation (vertices, rays, and lines).

EXAMPLES:

sage: p = polytopes.cyclic_polytope(3,4)
sage: vg = p.Vrep_generator()
sage: 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 V-representation. Each entry is either a vertex, a ray, or a line.

See sage.geometry.polyhedron.constructor for a definition of vertex/ray/line.

INPUT:

index – either an integer or None

OUTPUT:

The optional argument is an index running from 0 to self.n_Vrepresentation()-1. If present, the V-representation object at the given index will be returned. Without an argument, returns the list of all V-representation objects.

EXAMPLES:

sage: p = polytopes.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 free module.

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

a_maximal_chain()¶

Return a maximal chain of the face lattice in increasing order.

EXAMPLES:

sage: P = polytopes.cube()
sage: P.a_maximal_chain()
[A -1-dimensional face of a Polyhedron in ZZ^3,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 8 vertices]
sage: P = polytopes.cube()
sage: chain = P.a_maximal_chain(); chain
[A -1-dimensional face of a Polyhedron in ZZ^3,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 8 vertices]
sage: [face.ambient_V_indices() for face in chain]
[(), (5,), (0, 5), (0, 3, 4, 5), (0, 1, 2, 3, 4, 5, 6, 7)]

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 V-representation object are adjacent.

Two vertices are adjacent if they are the endpoints of an edge, that is, a one-dimensional face. For unbounded polyhedra this clearly needs to be generalized and we define two V-representation objects (see sage.geometry.polyhedron.constructor) to be adjacent if they together generate a one-face. There are three possible combinations:

Two vertices can bound a finite-length edge.
A vertex and a ray can generate a half-infinite 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 half-plane:

sage: half_plane = Polyhedron(ieqs=[(0,1,0)])
sage: half_plane.Hrepresentation()
(An inequality (1, 0) x + 0 >= 0,)

Its (non-unique) V-representation consists of a vertex, a ray, and a line. The only edge is spanned by the vertex and the line generator, so they are adjacent:

sage: half_plane.Vrepresentation()
(A line in the direction (0, 1), A ray in the direction (1, 0), A vertex at (0, 0))
sage: half_plane.vertex_adjacency_matrix()
[0 0 1]
[0 0 0]
[1 0 0]

In one dimension higher, that is for a half-space in 3 dimensions, there is no one-dimensional face. Hence nothing is adjacent:

sage: Polyhedron(ieqs=[(0,1,0,0)]).vertex_adjacency_matrix()
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]

EXAMPLES:

In a bounded polygon, every vertex has precisely two adjacent ones:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)])
sage: for v in P.Vrep_generator():
....:     print("{} {}".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 V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
....:                rays=[(0,1)])
sage: for v in P.Vrep_generator():
....:       print("{} {}".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 V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
....:                rays=[(0,1), (1,1)])
sage: for v in P.Vrep_generator():
....:     print("{} {}".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)

The vertex adjacency matrix has base ring integers. This way one can express various counting questions:

sage: P = polytopes.cube()
sage: Q = P.stack(P.faces(2)[0])
sage: M = Q.vertex_adjacency_matrix()
sage: sum(M)
(4, 4, 3, 3, 4, 4, 4, 3, 3)
sage: G = Q.vertex_graph()
sage: G.degree()
[4, 4, 3, 3, 4, 4, 4, 3, 3]

affine_hull(*args, **kwds)¶

Return the affine hull of self as a polyhedron.

EXAMPLES:

sage: half_plane_in_space = Polyhedron(ieqs=[(0,1,0,0)], eqns=[(0,0,0,1)])
sage: half_plane_in_space.affine_hull().Hrepresentation()
(An equation (0, 0, 1) x + 0 == 0,)

sage: polytopes.cube().affine_hull().is_universe()
True

affine_hull_manifold(name=None, latex_name=None, start_index=0, ambient_space=None, ambient_chart=None, names=None, **kwds)¶

Return the affine hull of self as a manifold.

If self is full-dimensional, it is just the ambient Euclidean space. Otherwise, it is a Riemannian submanifold of the ambient Euclidean space.

INPUT:

ambient_space – a EuclideanSpace of the ambient dimension (default: the manifold of ambient_chart, if provided; otherwise, a new instance of EuclideanSpace).
ambient_chart – a chart on ambient_space.
names – names for the coordinates on the affine hull.
optional arguments accepted by affine_hull_projection().

The default chart is determined by the optional arguments of affine_hull_projection().

EXAMPLES:

sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]);  triangle
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: A = triangle.affine_hull_manifold(name='A'); A
2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3
sage: A.embedding().display()
A → E^3
   (x0, x1) ↦ (x, y, z) = (t0 + x0, t0 + x1, t0 - x0 - x1 + 1)
sage: A.embedding().inverse().display()
E^3 → A
   (x, y, z) ↦ (x0, x1) = (x, y)
sage: A.adapted_chart()
[Chart (E^3, (x0_E3, x1_E3, t0_E3))]
sage: A.normal().display()
n = 1/3*sqrt(3) e_x + 1/3*sqrt(3) e_y + 1/3*sqrt(3) e_z
sage: A.induced_metric()       # Need to call this before volume_form
Riemannian metric gamma on the 2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3
sage: A.volume_form()
2-form eps_gamma on the 2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3

Orthogonal version:

sage: A = triangle.affine_hull_manifold(name='A', orthogonal=True); A
2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3
sage: A.embedding().display()
A → E^3
   (x0, x1) ↦ (x, y, z) = (t0 - 1/2*x0 - 1/3*x1 + 1, t0 + 1/2*x0 - 1/3*x1, t0 + 2/3*x1)
sage: A.embedding().inverse().display()
E^3 → A
   (x, y, z) ↦ (x0, x1) = (-x + y + 1, -1/2*x - 1/2*y + z + 1/2)

Arrangement of affine hull of facets:

sage: D = polytopes.dodecahedron()
sage: E3 = EuclideanSpace(3)
sage: submanifolds = [
....:     F.as_polyhedron().affine_hull_manifold(name=f'F{i}', orthogonal=True, ambient_space=E3)
....:     for i, F in enumerate(D.facets())]
sage: sum(FM.plot({}, srange(-2, 2, 0.1), srange(-2, 2, 0.1), opacity=0.2)  # not tested
....:     for FM in submanifolds) + D.plot()
Graphics3d Object

Full-dimensional case:

sage: cube = polytopes.cube(); cube
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: cube.affine_hull_manifold()
Euclidean space E^3

affine_hull_projection(as_polyhedron, as_affine_map=None, orthogonal=False, orthonormal=False, extend=False, minimal=False, return_all_data=False, as_convex_set=False)¶

Return the polyhedron projected into its affine hull.

Each polyhedron is contained in some smallest affine subspace (possibly the entire ambient space) – its affine hull. We provide an affine linear map that projects the ambient space of the polyhedron to the standard Euclidean space of dimension of the polyhedron, which restricts to a bijection from the affine hull.

The projection map is not unique; some parameters control the choice of the map. Other parameters control the output of the function.

INPUT:

as_polyhedron (or as_convex_set) – (boolean or the default None) and
as_affine_map – (boolean, default False) control the output

The default as_polyhedron=None translates to as_polyhedron=not as_affine_map, therefore to as_polyhedron=True if nothing is specified.

If exactly one of either as_polyhedron or as_affine_map is set, then either a polyhedron or the affine transformation is returned. The affine transformation sends the embedded polytope to a fulldimensional one. It is given as a pair (A, b), where A is a linear transformation and \(b\) is a vector, and the affine transformation sends v to A(v)+b.

If both as_polyhedron and as_affine_map are set, then both are returned, encapsulated in an instance of AffineHullProjectionData.
return_all_data – (boolean, default False)

If set, then as_polyhedron and as_affine_map will set (possibly overridden) and additional (internal) data concerning the transformation is returned. Everything is encapsulated in an instance of AffineHullProjectionData in this case.
orthogonal – boolean (default: False); if True, provide an orthogonal transformation.
orthonormal – boolean (default: False); if True, provide an orthonormal transformation. If the base ring does not provide the necessary square roots, the extend parameter needs to be set to True.
extend – boolean (default: False); if True, allow base ring to be extended if necessary. This becomes relevant when requiring an orthonormal transformation.
minimal – boolean (default: False); if True, when doing an extension, it computes the minimal base ring of the extension, otherwise the base ring is AA.

OUTPUT:

A full-dimensional polyhedron or an affine transformation, depending on the parameters as_polyhedron and as_affine_map, or an instance of AffineHullProjectionData containing all data (parameter return_all_data).

If the output is an instance of AffineHullProjectionData, the following fields may be set:

image – the projection of the original polyhedron
projection_map – the affine map as a pair whose first component is a linear transformation and its second component a shift; see above.
section_map – an affine map as a pair whose first component is a linear transformation and its second component a shift. It maps the codomain of affine_map to the affine hull of self. It is a right inverse of projection_map.

Note that all of these data are compatible.

Todo

make the parameters orthogonal and orthonormal work with unbounded polyhedra.

EXAMPLES:

sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]);  triangle
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: triangle.affine_hull_projection()
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices

sage: half3d = Polyhedron(vertices=[(3,2,1)], rays=[(1,0,0)])
sage: half3d.affine_hull_projection().Vrepresentation()
(A ray in the direction (1), A vertex at (3))

The resulting affine hulls depend on the parameter orthogonal and orthonormal:

sage: L = Polyhedron([[1,0],[0,1]]); L
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: A = L.affine_hull_projection(); A
A 1-dimensional 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_projection(orthogonal=True); A
A 1-dimensional 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_projection(orthonormal=True)
Traceback (most recent call last):
...
ValueError: the base ring needs to be extended; try with "extend=True"
sage: A = L.affine_hull_projection(orthonormal=True, extend=True); A
A 1-dimensional polyhedron in AA^1 defined as the convex hull of 2 vertices
sage: A.vertices()
(A vertex at (1.414213562373095?), A vertex at (0.?e-18))

More generally:

sage: S = polytopes.simplex(); S
A 3-dimensional 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_projection(); A
A 3-dimensional 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_projection(orthogonal=True); A
A 3-dimensional 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_projection(orthonormal=True, extend=True); A
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 4 vertices
sage: A.vertices()
(A vertex at (0.7071067811865475?, 0.4082482904638630?, 1.154700538379252?),
 A vertex at (0.7071067811865475?, 1.224744871391589?, 0.?e-18),
 A vertex at (1.414213562373095?, 0.?e-18, 0.?e-18),
 A vertex at (0.?e-18, 0.?e-18, 0.?e-18))

With the parameter minimal one can get a minimal base ring:

sage: s = polytopes.simplex(3)
sage: s_AA = s.affine_hull_projection(orthonormal=True, extend=True)
sage: s_AA.base_ring()
Algebraic Real Field
sage: s_full = s.affine_hull_projection(orthonormal=True, extend=True, minimal=True)
sage: s_full.base_ring()
Number Field in a with defining polynomial y^4 - 4*y^2 + 1 with a = 0.5176380902050415?

More examples with the orthonormal parameter:

sage: P = polytopes.permutahedron(3); P
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices
sage: set([F.as_polyhedron().affine_hull_projection(orthonormal=True, extend=True).volume() for F in P.affine_hull_projection().faces(1)]) == {1, sqrt(AA(2))}
True
sage: set([F.as_polyhedron().affine_hull_projection(orthonormal=True, extend=True).volume() for F in P.affine_hull_projection(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_projection(orthogonal=True)
A 2-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^2 defined as the convex hull of 5 vertices
sage: F.affine_hull_projection(orthonormal=True, extend=True)
A 2-dimensional 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 1-dimensional polyhedron in (Number Field in sqrt2 with defining polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^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_projection(orthonormal=True); A
A 1-dimensional polyhedron in (Number Field in sqrt2 with defining polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^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 1-dimensional polyhedron in (Number Field in sqrt3 with defining polynomial x^2 - 3 with sqrt3 = 1.732050807568878?)^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_projection(orthonormal=True)
Traceback (most recent call last):
...
ValueError: the base ring needs to be extended; try with "extend=True"
sage: A = P.affine_hull_projection(orthonormal=True, extend=True); A
A 1-dimensional 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_projection())
True
sage: P.is_combinatorially_isomorphic(P.affine_hull_projection(orthogonal=True))
True
sage: P.is_combinatorially_isomorphic(P.affine_hull_projection(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_projection(orthonormal=True, extend=True)
sage: _, c= P.is_inscribed(certificate=True)
sage: c
(0.4721359549995794?, 0.6498393924658126?)
sage: circumradius = (c-vector(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_projection(orthonormal=True, extend=True)
sage: Pgonal = Pentagon.affine_hull_projection(orthogonal=True)
sage: A, b = Pentagon.affine_hull_projection(orthogonal=True, as_affine_map=True)
sage: Adet = (A.matrix().transpose()*A.matrix()).det()
sage: Pnormal.volume()
1.53406271079097?
sage: Pgonal.volume()/Adet.sqrt(extend=True)
-80*(55*sqrt(5) - 123)/sqrt(-6368*sqrt(5) + 14240)
sage: Pgonal.volume()/AA(Adet).sqrt().n(digits=20)
1.5340627107909646813
sage: AA(Pgonal.volume()^2) == (Pnormal.volume()^2)*AA(Adet)
True

Another example with as_affine_map=True:

sage: P = polytopes.permutahedron(4)
sage: A, b = P.affine_hull_projection(orthonormal=True, as_affine_map=True, extend=True)
sage: Q = P.affine_hull_projection(orthonormal=True, extend=True)
sage: Q.center()
(0.7071067811865475?, 1.224744871391589?, 1.732050807568878?)
sage: A(P.center()) + b == Q.center()
True

For unbounded, non full-dimensional polyhedra, the orthogonal=True and orthonormal=True is not implemented:

sage: P = Polyhedron(ieqs=[[0, 1, 0], [0, 0, 1], [0, 0, -1]]); P
A 1-dimensional 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_projection(orthogonal=True)
Traceback (most recent call last):
...
NotImplementedError: "orthogonal=True" and "orthonormal=True" work only for compact polyhedra
sage: P.affine_hull_projection(orthonormal=True)
Traceback (most recent call last):
...
NotImplementedError: "orthogonal=True" and "orthonormal=True" work only for compact polyhedra

Setting as_affine_map to True without orthogonal or orthonormal set to True:

sage: S = polytopes.simplex()
sage: S.affine_hull_projection(as_affine_map=True)
(Vector space morphism represented by the matrix:
 [1 0 0]
 [0 1 0]
 [0 0 1]
 [0 0 0]
 Domain: Vector space of dimension 4 over Rational Field
 Codomain: Vector space of dimension 3 over Rational Field,
 (0, 0, 0))

If the polyhedron is full-dimensional, it is returned:

sage: polytopes.cube().affine_hull_projection()
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: polytopes.cube().affine_hull_projection(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))

Return polyhedron and affine map:

sage: S = polytopes.simplex(2)
sage: data = S.affine_hull_projection(orthogonal=True,
....:                                 as_polyhedron=True,
....:                                 as_affine_map=True); data
AffineHullProjectionData(image=A 2-dimensional polyhedron in QQ^2
        defined as the convex hull of 3 vertices,
    projection_linear_map=Vector space morphism represented by the matrix:
        [  -1 -1/2]
        [   1 -1/2]
        [   0    1]
        Domain: Vector space of dimension 3 over Rational Field
        Codomain: Vector space of dimension 2 over Rational Field,
    projection_translation=(1, 1/2),
    section_linear_map=None,
    section_translation=None)

Return all data:

sage: data = S.affine_hull_projection(orthogonal=True, return_all_data=True); data
AffineHullProjectionData(image=A 2-dimensional polyhedron in QQ^2
        defined as the convex hull of 3 vertices,
    projection_linear_map=Vector space morphism represented by the matrix:
        [  -1 -1/2]
        [   1 -1/2]
        [   0    1]
        Domain: Vector space of dimension 3 over Rational Field
        Codomain: Vector space of dimension 2 over Rational Field,
    projection_translation=(1, 1/2),
    section_linear_map=Vector space morphism represented by the matrix:
        [-1/2  1/2    0]
        [-1/3 -1/3  2/3]
        Domain: Vector space of dimension 2 over Rational Field
        Codomain: Vector space of dimension 3 over Rational Field, section_translation=(1, 0, 0))

The section map is a right inverse of the projection map:

sage: data.image.linear_transformation(data.section_linear_map.matrix().transpose()) + data.section_translation == S
True

Same without orthogonal=True:

sage: data = S.affine_hull_projection(return_all_data=True); data
AffineHullProjectionData(image=A 2-dimensional polyhedron in ZZ^2
        defined as the convex hull of 3 vertices,
    projection_linear_map=Vector space morphism represented by the matrix:
        [1 0]
        [0 1]
        [0 0]
        Domain: Vector space of dimension 3 over Rational Field
        Codomain: Vector space of dimension 2 over Rational Field, projection_translation=(0, 0),
    section_linear_map=Vector space morphism represented by the matrix:
        [ 1  0 -1]
        [ 0  1 -1]
        Domain: Vector space of dimension 2 over Rational Field
        Codomain: Vector space of dimension 3 over Rational Field, section_translation=(0, 0, 1))
sage: data.image.linear_transformation(data.section_linear_map.matrix().transpose()) + data.section_translation == S
True

sage: P0 = Polyhedron(
....:     ieqs=[(0, -1, 0, 1, 1, 1), (0, 1, 1, 0, -1, -1), (0, -1, 1, 1, 0, 0),
....:           (0, 1, 0, 0, 0, 0), (0, 0, 1, 1, -1, -1), (0, 0, 0, 0, 0, 1),
....:           (0, 0, 0, 0, 1, 0), (0, 0, 0, 1, 0, -1), (0, 0, 1, 0, 0, 0)])
sage: P = P0.intersection(Polyhedron(eqns=[(-1, 1, 1, 1, 1, 1)]))
sage: P.dim()
4
sage: P.affine_hull_projection(orthogonal=True, as_affine_map=True)[0]
Vector space morphism represented by the matrix:
[    0     0     0   1/3]
[ -2/3  -1/6     0 -1/12]
[  1/3  -1/6   1/2 -1/12]
[    0   1/2     0 -1/12]
[  1/3  -1/6  -1/2 -1/12]
Domain: Vector space of dimension 5 over Rational Field
Codomain: Vector space of dimension 4 over Rational Field

ambient(base_field=None)¶

Return the ambient vector space.

It is the ambient free module (Vrepresentation_space()) tensored with a field.

INPUT:

base_field – (default: the fraction field of the base ring) a field.

EXAMPLES:

sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.ambient_vector_space()
Vector space of dimension 4 over Rational Field
sage: poly_test.ambient_vector_space() is poly_test.ambient()
True

sage: poly_test.ambient_vector_space(AA)
Vector space of dimension 4 over Algebraic Real Field
sage: poly_test.ambient_vector_space(RR)
Vector space of dimension 4 over Real Field with 53 bits of precision
sage: poly_test.ambient_vector_space(SR)
Vector space of dimension 4 over Symbolic Ring

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 free module.

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

ambient_vector_space(base_field=None)¶

Return the ambient vector space.

It is the ambient free module (Vrepresentation_space()) tensored with a field.

INPUT:

base_field – (default: the fraction field of the base ring) a field.

EXAMPLES:

sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.ambient_vector_space()
Vector space of dimension 4 over Rational Field
sage: poly_test.ambient_vector_space() is poly_test.ambient()
True

sage: poly_test.ambient_vector_space(AA)
Vector space of dimension 4 over Algebraic Real Field
sage: poly_test.ambient_vector_space(RR)
Vector space of dimension 4 over Real Field with 53 bits of precision
sage: poly_test.ambient_vector_space(SR)
Vector space of dimension 4 over Symbolic Ring

an_affine_basis()¶

Return points in self that are a basis for the affine span of the polytope.

This implementation of the method ConvexSet_base.an_affine_basis() for polytopes guarantees the following:

All points are vertices.
The basis is obtained by considering a maximal chain of faces in the face lattice and picking for each cover relation one vertex that is in the difference. Thus this method is independent of the concrete realization of the polytope.

EXAMPLES:

sage: P = polytopes.cube()
sage: P.an_affine_basis()
[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: P = polytopes.permutahedron(5)
sage: P.an_affine_basis()
[A vertex at (1, 2, 3, 5, 4),
 A vertex at (2, 1, 3, 5, 4),
 A vertex at (1, 3, 2, 5, 4),
 A vertex at (4, 1, 3, 5, 2),
 A vertex at (4, 2, 5, 3, 1)]

The method is not implemented for unbounded polyhedra:

sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
sage: p.an_affine_basis()
Traceback (most recent call last):
...
NotImplementedError: this function is not implemented for unbounded polyhedra

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 Library

cdd CDD

normaliz normaliz

polymake polymake

field 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, North-Holland 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 3-dimensional 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 3-dimensional 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 2-dimensional 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 2-dimensional 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, see Polyhedron(). If None (the default), attempt to keep the same backend. Otherwise, use the same defaulting behavior as described there.

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 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.base_extend(QQ)
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.base_extend(QQ) == P
True

base_ring()¶

Return the base ring.

OUTPUT:

The ring over which the polyhedron is defined. Must be a sub-ring 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 floating-point arithmetic), or
AA (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 cross-polytopes are cross-polytopes:

sage: q2 = [list(v) for v in polytopes.cross_polytope(4).vertex_generator()]
sage: [v in q2 for v in q]
[True, True, True, True, True, True, True, True]

boundary_complex()¶

Return the simplicial complex given by the boundary faces of self, if it is simplicial.

OUTPUT:

A (spherical) simplicial complex

EXAMPLES:

The boundary complex of the octahedron:

sage: oc = polytopes.octahedron()
sage: sc_oc = oc.boundary_complex()
sage: fl_oc = oc.face_lattice()
sage: fl_sc = sc_oc.face_poset()
sage: [len(x) for x in fl_oc.level_sets()]
[1, 6, 12, 8, 1]
sage: [len(x) for x in fl_sc.level_sets()]
[6, 12, 8]
sage: sc_oc.euler_characteristic()
2
sage: sc_oc.homology()
{0: 0, 1: 0, 2: Z}

The polyhedron should be simplicial:

sage: c = polytopes.cube()
sage: c.boundary_complex()
Traceback (most recent call last):
...
NotImplementedError: this function is only implemented for simplicial polytopes

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 non-empty polytope.

INPUT:

integral – Boolean (default: False). Whether to only allow integral coordinates in the bounding box.
integral_hull – Boolean (default: False). If True, return a box containing the integral points of the polytope, or None, None if it is known that the polytope has no integral points.

OUTPUT:

A pair of tuples (box_min, box_max) where box_min are the coordinates of a point bounding the coordinates of the polytope from below and box_max bounds the coordinates from above.

EXAMPLES:

sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box()
((1/3, 1/3), (2/3, 2/3))
sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral=True)
((0, 0), (1, 1))
sage: 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))

cartesian_product(other)¶

Return the Cartesian product.

INPUT:

other – a Polyhedron_base

OUTPUT:

The Cartesian product of self and other with a suitable base ring to encompass the two.

EXAMPLES:

sage: P1 = Polyhedron([[0],[1]], base_ring=ZZ)
sage: P2 = Polyhedron([[0],[1]], base_ring=QQ)
sage: P1.product(P2)
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices

The Cartesian product is the product in the semiring of polyhedra:

sage: P1 * P1
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: P1 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P2 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: 2 * P1
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices
sage: P1 * 2.0
A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices

An alias is cartesian_product():

sage: P1.cartesian_product(P2) == P1.product(P2)
True

cdd_Hrepresentation()¶

Write the inequalities/equations data of the polyhedron in cdd’s H-representation format.

See also

write_cdd_Hrepresentation() – export the polyhedron as a H-representation to a file.

OUTPUT: a string

EXAMPLES:

sage: p = polytopes.hypercube(2)
sage: print(p.cdd_Hrepresentation())
H-representation
begin
 4 3 rational
 1 -1 0
 1 0 -1
 1 1 0
 1 0 1
end


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 V-representation format.

See also

write_cdd_Vrepresentation() – export the polyhedron as a V-representation to a file.

OUTPUT: a string

EXAMPLES:

sage: q = Polyhedron(vertices = [[1,1],[0,0],[1,0],[0,1]])
sage: print(q.cdd_Vrepresentation())
V-representation
begin
 4 3 rational
 1 0 0
 1 0 1
 1 1 0
 1 1 1
end

center()¶

Return the average of the vertices.

See also

representative_point().

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)

centroid(engine='auto', **kwds)¶

Return the center of the mass of the polytope.

The mass is taken with respect to the induced Lebesgue measure, see volume().

If the polyhedron is not compact, a NotImplementedError is raised.

INPUT:

engine – either ‘auto’ (default), ‘internal’, ‘TOPCOM’, or ‘normaliz’. The ‘internal’ and ‘TOPCOM’ 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.
**kwds – keyword arguments that are passed to the triangulation engine (see triangulate()).

OUTPUT: The centroid as vector.

ALGORITHM:

We triangulate the polytope and find the barycenter of the simplices. We add the individual barycenters weighted by the fraction of the total mass.

EXAMPLES:

sage: P = polytopes.hypercube(2).pyramid()
sage: P.centroid()
(1/4, 0, 0)

sage: P = polytopes.associahedron(['A',2])
sage: P.centroid()
(2/21, 2/21)

sage: P = polytopes.permutahedron(4, backend='normaliz')  # optional - pynormaliz
sage: P.centroid()                                        # optional - pynormaliz
(5/2, 5/2, 5/2, 5/2)

The method is not implemented for unbounded polyhedra:

sage: P = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
sage: P.centroid()
Traceback (most recent call last):
...
NotImplementedError: the polyhedron is not compact

The centroid of an empty polyhedron is not defined:

sage: Polyhedron().centroid()
Traceback (most recent call last):
...
ZeroDivisionError: rational division by zero

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 or None (default), see Polyhedron(). If None (the default), attempt to keep the same backend. Otherwise, use the same defaulting behavior as described there.

EXAMPLES:

sage: P = Polyhedron(vertices=[(1,0), (0,1)], rays=[(1,1)], base_ring=QQ); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.change_ring(ZZ)
A 2-dimensional 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

sage: P = polytopes.regular_polygon(3); P
A 2-dimensional polyhedron in AA^2 defined as the convex hull of 3 vertices
sage: P.vertices()
(A vertex at (0.?e-16, 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

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 into RDF may cause a loss of data:

sage: P = Polyhedron([[2/3,0],[6666666666666667/10^16,0]], base_ring=AA); P
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices
sage: Q = P.change_ring(RDF); Q
A 0-dimensional polyhedron in RDF^2 defined as the convex hull of 1 vertex
sage: P.n_vertices() == Q.n_vertices()
False

combinatorial_automorphism_group(vertex_graph_only=False)¶

Computes the combinatorial automorphism group.

If vertex_graph_only is True, the automorphism group of the vertex-edge graph of the polyhedron is returned. Otherwise the automorphism group of the vertex-facet 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 is True: The automorphism group of the vertex-edge graph of the polyhedron
if vertex_graph_only is False (default): The automorphism group of the vertex-facet graph of the polyhedron, see vertex_facet_graph(). This group is isomorphic to the automorphism group of the face lattice of the polyhedron.

NOTE:

Depending on vertex_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 of the vertex graph only exchange vertices with vertices:

sage: P = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)])
sage: P.combinatorial_automorphism_group(vertex_graph_only=True)
Permutation Group with generators [(A vertex at (1,0),A vertex at (1,1))]

This shows an example of two polytopes whose vertex-edge 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.hasse_diagram().automorphism_group()
sage: C.combinatorial_automorphism_group().is_isomorphic(CG)
True
sage: QG = Q.hasse_diagram().automorphism_group()
sage: Q.combinatorial_automorphism_group().is_isomorphic(QG)
True

combinatorial_polyhedron()¶

Return the combinatorial type of self.

See sage.geometry.polyhedron.combinatorial_polyhedron.base.CombinatorialPolyhedron.

EXAMPLES:

sage: polytopes.cube().combinatorial_polyhedron()
A 3-dimensional combinatorial polyhedron with 6 facets

sage: polytopes.cyclic_polytope(4,10).combinatorial_polyhedron()
A 4-dimensional combinatorial polyhedron with 35 facets

sage: Polyhedron(rays=[[0,1], [1,0]]).combinatorial_polyhedron()
A 2-dimensional combinatorial polyhedron with 2 facets

contains(point)¶

Test whether the polyhedron contains the given point.

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 0-dimensional 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 set-theoretic union of the two polyhedra.

INPUT:

other – a Polyhedron

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 in base_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 non-negative integer.

EXAMPLES:

sage: simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]])
sage: simplex.dim()
3
sage: simplex.ambient_dim()
4

The empty set is a special case (trac 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 non-negative integer.

EXAMPLES:

sage: simplex = Polyhedron(vertices = [[1,0,0,0],[0,0,0,1],[0,1,0,0],[0,0,1,0]])
sage: simplex.dim()
3
sage: simplex.ambient_dim()
4

The empty set is a special case (trac 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 and other.

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 of self.

INPUT:

other – a Polyhedron_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 2-dimensional 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

join() subdirect_sum()

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() or equation_generator() instead to iterate over the list of Equation objects.

EXAMPLES:

sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
sage: test_p.equations_list()
[[-10, 1, 1, 1, 1]]

f_vector(num_threads=None, parallelization_depth=None)¶

Return the f-vector.

INPUT:

num_threads – integer (optional); specify the number of threads; otherwise determined by ncpus()
parallelization_depth – integer (optional); specify how deep in the lattice the parallelization is done

OUTPUT:

Return a vector whose \(i\)-th entry is the number of \(i-2\)-dimensional faces of the polytope.

Note

The vertices as given by Polyhedron_base.vertices() do not need to correspond to \(0\)-dimensional faces. If a polyhedron contains \(k\) lines they correspond to \(k\)-dimensional faces. See example below

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)

sage: polytopes.cyclic_polytope(4,10).f_vector()
(1, 10, 45, 70, 35, 1)

sage: polytopes.hypercube(5).f_vector()
(1, 32, 80, 80, 40, 10, 1)

Polyhedra with lines do not have \(0\)-faces:

sage: Polyhedron(ieqs=[[1,-1,0,0],[1,1,0,0]]).f_vector()
(1, 0, 0, 2, 1)

However, the method Polyhedron_base.vertices() returns two points that belong to the Vrepresentation:

sage: P = Polyhedron(ieqs=[[1,-1,0],[1,1,0]])
sage: P.vertices()
(A vertex at (1, 0), A vertex at (-1, 0))
sage: P.f_vector()
(1, 0, 2, 1)

face_fan()¶

Return the face fan of a compact rational polyhedron.

OUTPUT:

A fan of the ambient space as a RationalPolyhedralFan.

See also

normal_fan().

EXAMPLES:

sage: T = polytopes.cuboctahedron()
sage: T.face_fan()
Rational polyhedral fan in 3-d 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 2-d 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_generator(face_dimension=None, dual=None)¶

Return an iterator over the faces of given dimension.

If dimension is not specified return an iterator over all faces.

INPUT:

face_dimension – integer (default None), yield only faces of this dimension if specified
dual – boolean (default None); if True, generate the faces using the vertices; if False, generate the faces using the facets; if None, pick automatically

OUTPUT:

A FaceIterator_geom. This class iterates over faces as PolyhedronFace. See face for details. The order is random but fixed.

EXAMPLES:

sage: P = polytopes.cube()
sage: it = P.face_generator()
sage: it
Iterator over the faces of a 3-dimensional polyhedron in ZZ^3
sage: list(it)
[A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 8 vertices,
 A -1-dimensional face of a Polyhedron in ZZ^3,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices]

 sage: P = polytopes.hypercube(4)
 sage: list(P.face_generator(2))[:4]
 [A 2-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 4 vertices,
  A 2-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 4 vertices,
  A 2-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 4 vertices,
  A 2-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 4 vertices]

If a polytope has more facets than vertices, the dual mode is chosen:

sage: P = polytopes.cross_polytope(3)
sage: list(P.face_generator())
[A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 6 vertices,
 A -1-dimensional face of a Polyhedron in ZZ^3,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices,
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices,
 A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices]

The face iterator can also be slightly modified. In non-dual mode we can skip subfaces of the current (proper) face:

sage: P = polytopes.cube()
sage: it = P.face_generator(dual=False)
sage: _ = next(it), next(it)
sage: face = next(it)
sage: face.ambient_H_indices()
(5,)
sage: it.ignore_subfaces()
sage: face = next(it)
sage: face.ambient_H_indices()
(4,)
sage: it.ignore_subfaces()
sage: [face.ambient_H_indices() for face in it]
[(3,),
 (2,),
 (1,),
 (0,),
 (2, 3),
 (1, 3),
 (1, 2, 3),
 (1, 2),
 (0, 2),
 (0, 1, 2),
 (0, 1)]

In dual mode we can skip supfaces of the current (proper) face:

sage: P = polytopes.cube()
sage: it = P.face_generator(dual=True)
sage: _ = next(it), next(it)
sage: face = next(it)
sage: face.ambient_V_indices()
(7,)
sage: it.ignore_supfaces()
sage: next(it)
A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex
sage: face = next(it)
sage: face.ambient_V_indices()
(5,)
sage: it.ignore_supfaces()
sage: [face.ambient_V_indices() for face in it]
[(4,),
 (3,),
 (2,),
 (1,),
 (0,),
 (1, 6),
 (3, 4),
 (2, 3),
 (0, 3),
 (0, 1, 2, 3),
 (1, 2),
 (0, 1)]

In non-dual mode, we cannot skip supfaces:

sage: it = P.face_generator(dual=False)
sage: _ = next(it), next(it)
sage: next(it)
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: it.ignore_supfaces()
Traceback (most recent call last):
...
ValueError: only possible when in dual mode

In dual mode, we cannot skip subfaces:

sage: it = P.face_generator(dual=True)
sage: _ = next(it), next(it)
sage: next(it)
A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex
sage: it.ignore_subfaces()
Traceback (most recent call last):
...
ValueError: only possible when not in dual mode

We can only skip sub-/supfaces of proper faces:

sage: it = P.face_generator(dual=False)
sage: next(it)
A 3-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: it.ignore_subfaces()
Traceback (most recent call last):
...
ValueError: iterator not set to a face yet

See also

FaceIterator_geom.

ALGORITHM:

See FaceIterator.

face_lattice()¶

Return the face-lattice poset.

OUTPUT:

A FinitePoset. Elements are given as PolyhedronFace.

In the case of a full-dimensional polytope, the faces are pairs (vertices, inequalities) of the spanning vertices and corresponding saturated inequalities. In general, a face is defined by a pair (V-rep. objects, H-rep. objects). The V-representation objects span the face, and the corresponding H-representation objects are those inequalities and equations that are saturated on the face.

The bottom-most element of the face lattice is the “empty face”. It contains no V-representation object. All H-representation objects are incident.

The top-most element is the “full face”. It is spanned by all V-representation objects. The incident H-representation objects are all equations and no inequalities.

In the case of a full-dimensional polytope, the “empty face” and the “full face” are the empty set (no vertices, all inequalities) and the full polytope (all vertices, no inequalities), respectively.

ALGORITHM:

See sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.

Note

The face lattice is not cached, as long as this creates a memory leak, see trac ticket #28982.

EXAMPLES:

sage: square = polytopes.hypercube(2)
sage: fl = square.face_lattice();fl
Finite lattice containing 10 elements
sage: list(f.ambient_V_indices() for f in fl)
[(), (0,), (1,), (0, 1), (2,), (1, 2), (3,), (0, 3), (2, 3), (0, 1, 2, 3)]
sage: poset_element = fl[5]
sage: a_face = poset_element
sage: a_face
A 1-dimensional face of a Polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: a_face.ambient_V_indices()
(1, 2)
sage: set(a_face.ambient_Vrepresentation()) ==             ....: set([square.Vrepresentation(1), square.Vrepresentation(2)])
True
sage: a_face.ambient_Vrepresentation()
(A vertex at (1, 1), A vertex at (-1, 1))
sage: a_face.ambient_Hrepresentation()
(An inequality (0, -1) x + 1 >= 0,)

A more complicated example:

sage: c5_10 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5] for i in range(1,11)])
sage: c5_10_fl = c5_10.face_lattice()
sage: [len(x) for x in c5_10_fl.level_sets()]
[1, 10, 45, 100, 105, 42, 1]

Note that if the polyhedron contains lines then there is a dimension gap between the empty face and the first non-empty face in the face lattice:

sage: line = Polyhedron(vertices=[(0,)], lines=[(1,)])
sage: [ fl.dim() for fl in line.face_lattice() ]
[-1, 1]

face_split(face)¶

Return the face splitting of the face face.

Splitting a face correspond to the bipyramid (see bipyramid()) of self where the two new vertices are placed above and below the center of face 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

one_point_suspension()

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: tuple(f.ambient_V_indices() for f in vertex_trunc1.faces(2))
((4, 5, 6, 7, 9),
 (0, 3, 4, 8, 9),
 (0, 1, 6, 7, 8),
 (7, 8, 9),
 (2, 3, 4, 5),
 (1, 2, 5, 6),
 (0, 1, 2, 3))
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: tuple(f.ambient_V_indices() for f in vertex_trunc2.faces(2))
((4, 5, 6, 7, 9),
 (0, 3, 4, 8, 9),
 (0, 1, 6, 7, 8),
 (7, 8, 9),
 (2, 3, 4, 5),
 (1, 2, 5, 6),
 (0, 1, 2, 3))
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)[11])
sage: edge_trunc.f_vector()
(1, 10, 15, 7, 1)
sage: tuple(f.ambient_V_indices() for f in edge_trunc.faces(2))
((0, 5, 6, 7),
 (1, 4, 5, 6, 8),
 (6, 7, 8, 9),
 (0, 2, 3, 7, 9),
 (1, 2, 8, 9),
 (0, 3, 4, 5),
 (1, 2, 3, 4))
 sage: face_trunc = Cube.face_truncation(Cube.faces(2)[2])
 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. See face for details. The order is random but fixed.

See also

face_generator(), facet().

EXAMPLES:

Here we find the vertex and face indices of the eight three-dimensional facets of the four-dimensional hypercube:

sage: p = polytopes.hypercube(4)
sage: list(f.ambient_V_indices() for f in p.faces(3))
[(0, 5, 6, 7, 8, 9, 14, 15),
 (1, 4, 5, 6, 10, 13, 14, 15),
 (1, 2, 6, 7, 8, 10, 11, 15),
 (8, 9, 10, 11, 12, 13, 14, 15),
 (0, 3, 4, 5, 9, 12, 13, 14),
 (0, 2, 3, 7, 8, 9, 11, 12),
 (1, 2, 3, 4, 10, 11, 12, 13),
 (0, 1, 2, 3, 4, 5, 6, 7)]

sage: face = p.faces(3)[3]
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()]
[8, 9, 10, 11, 12, 13, 14, 15]

sage: [ ([get_idx(_) for _ in face.ambient_Vrepresentation()],
....:    [get_idx(_) for _ in face.ambient_Hrepresentation()])
....:   for face in p.faces(3) ]
[([0, 5, 6, 7, 8, 9, 14, 15], [7]),
 ([1, 4, 5, 6, 10, 13, 14, 15], [6]),
 ([1, 2, 6, 7, 8, 10, 11, 15], [5]),
 ([8, 9, 10, 11, 12, 13, 14, 15], [4]),
 ([0, 3, 4, 5, 9, 12, 13, 14], [3]),
 ([0, 2, 3, 7, 8, 9, 11, 12], [2]),
 ([1, 2, 3, 4, 10, 11, 12, 13], [1]),
 ([0, 1, 2, 3, 4, 5, 6, 7], [0])]

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]

The facet adjacency matrix has base ring integers. This way one can express various counting questions:

sage: P = polytopes.cube()
sage: Q = P.stack(P.faces(2)[0])
sage: M = Q.facet_adjacency_matrix()
sage: sum(M)
(4, 4, 4, 4, 3, 3, 3, 3, 4)

facets()¶

Return the facets of the polyhedron.

Facets are the maximal nontrivial faces of polyhedra. The empty face and the polyhedron itself are trivial.

A facet of a \(d\)-dimensional polyhedron is a face of dimension \(d-1\). For \(d \neq 0\) the converse is true as well.

OUTPUT:

A tuple of PolyhedronFace. See face for details. The order is random but fixed.

See also

facets()

EXAMPLES:

Here we find the eight three-dimensional facets of the four-dimensional hypercube:

sage: p = polytopes.hypercube(4)
sage: p.facets()
(A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices)

This is the same result as explicitly finding the three-dimensional faces:

sage: dim = p.dimension()
sage: p.faces(dim-1)
(A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices,
 A 3-dimensional face of a Polyhedron in ZZ^4 defined as the convex hull of 8 vertices)

The 0-dimensional polyhedron does not have facets:

sage: P = Polyhedron([[0]])
sage: P.facets()
()

flag_f_vector(*args)¶

Return the flag f-vector.

For each \(-1 < i_0 < \dots < i_n < d\) the flag f-vector counts the number of flags \(F_0 \subset \dots \subset F_n\) with \(F_j\) of dimension \(i_j\) for each \(0 \leq j \leq n\), where \(d\) is the dimension of the polyhedron.

INPUT:

args – integers (optional); specify an entry of the flag-f-vector; must be an increasing sequence of integers

OUTPUT:

a dictionary, if no arguments were given
an Integer, if arguments were given

EXAMPLES:

Obtain the entire flag-f-vector:

sage: P = polytopes.twenty_four_cell()
sage: P.flag_f_vector()
    {(-1,): 1,
     (0,): 24,
     (0, 1): 192,
     (0, 1, 2): 576,
     (0, 1, 2, 3): 1152,
     (0, 1, 3): 576,
     (0, 2): 288,
     (0, 2, 3): 576,
     (0, 3): 144,
     (1,): 96,
     (1, 2): 288,
     (1, 2, 3): 576,
     (1, 3): 288,
     (2,): 96,
     (2, 3): 192,
     (3,): 24,
     (4,): 1}

Specify an entry:

sage: P.flag_f_vector(0,3)
144
sage: P.flag_f_vector(2)
96

Leading -1 and trailing entry of dimension are allowed:

sage: P.flag_f_vector(-1,0,3)
144
sage: P.flag_f_vector(-1,0,3,4)
144

One can get the number of trivial faces:

sage: P.flag_f_vector(-1)
1
sage: P.flag_f_vector(4)
1

Polyhedra with lines, have 0 entries accordingly:

sage: P = (Polyhedron(lines=[[1]]) * polytopes.cross_polytope(3))
sage: P.flag_f_vector()
{(-1,): 1,
 (0, 1): 0,
 (0, 1, 2): 0,
 (0, 1, 3): 0,
 (0, 2): 0,
 (0, 2, 3): 0,
 (0, 3): 0,
 (0,): 0,
 (1, 2): 24,
 (1, 2, 3): 48,
 (1, 3): 24,
 (1,): 6,
 (2, 3): 24,
 (2,): 12,
 (3,): 8,
 4: 1}

If the arguments are not stricly increasing or out of range, a key error is raised:

sage: P.flag_f_vector(-1,0,3,6)
Traceback (most recent call last):
...
KeyError: (0, 3, 6)
sage: P.flag_f_vector(-1,3,0)
Traceback (most recent call last):
...
KeyError: (3, 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, -1), (1, 0), (0, 1))

REFERENCES:

Lectures in Geometric Combinatorics, R.R.Thomas, 2006, AMS Press.

See also

:func`~sage.geometry.polyhedron.library.gale_transform_to_polyhedron`.

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, a ValueError is raised.

INPUT:

index – integer. The index of the integral point to be found. If this is not in [0, self.integral_point_count()), an IndexError is raised.
**kwds – optional keyword parameters that are passed to self.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

integral_points_count().

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.

..NOTE:

The graph of a polyhedron with lines has no vertices,
as the polyhedron has no vertices (`0`-faces).

The method :meth:`Polyhedron_base:vertices` returns
the defining points in this case.

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

The graph of an unbounded polyhedron is the graph of the bounded complex:

sage: open_triangle = Polyhedron(vertices=[[1,0], [0,1]],
....:                            rays    =[[1,1]])
sage: open_triangle.vertex_graph()
Graph on 2 vertices

The graph of a polyhedron with lines has no vertices:

sage: line = Polyhedron(lines=[[0,1]])
sage: line.vertex_graph()
Graph on 0 vertices

greatest_common_subface_of_Hrep(*Hrepresentatives)¶

Return the largest face that is contained in Hrepresentatives.

INPUT:

Hrepresentatives – facets or indices of Hrepresentatives; the indices are assumed to be the indices of the Hrepresentation

OUTPUT: a PolyhedronFace

EXAMPLES:

sage: P = polytopes.permutahedron(5)
sage: P.meet_of_Hrep()
A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 120 vertices
sage: P.meet_of_Hrep(1)
A 3-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 24 vertices
sage: P.meet_of_Hrep(4)
A 3-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 12 vertices
sage: P.meet_of_Hrep(1,3,7)
A 1-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 2 vertices
sage: P.meet_of_Hrep(1,3,7).ambient_H_indices()
(0, 1, 3, 7)

The indices are the indices of the Hrepresentation. 0 corresponds to an equation and is ignored:

sage: P.meet_of_Hrep(0)
A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 120 vertices

The input is flexible:

sage: P.meet_of_Hrep(P.facets()[-1], P.inequalities()[2], 7)
A 1-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 2 vertices

The Hrepresentatives must belong to self:

sage: P = polytopes.cube(backend='ppl')
sage: Q = polytopes.cube(backend='field')
sage: f = P.facets()[0]
sage: P.meet_of_Hrep(f)
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: Q.meet_of_Hrep(f)
Traceback (most recent call last):
...
ValueError: not a facet of ``self``
sage: f = P.inequalities()[0]
sage: P.meet_of_Hrep(f)
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: Q.meet_of_Hrep(f)
Traceback (most recent call last):
...
ValueError: not a facet of ``self``

h_star_vector()¶

Return the \(h^*\)-vector of the lattice polytope.

The \(h^*\)-vector records the coefficients of the polynomial in the numerator of the Ehrhart series of a lattice polytope.

INPUT:

self – A lattice polytope.

OUTPUT:

A list whose entries give the \(h^*\)-vector.

EXAMPLES:

The \(h^*\)-vector of a unimodular simplex S (a simplex with volume = \(\frac{1}{dim(S)!}\)) is always 1. Here we test this on simplices up to dimension 3:

sage: s1 = polytopes.simplex(1,backend='normaliz')              # optional - pynormaliz
sage: s2 = polytopes.simplex(2,backend='normaliz')              # optional - pynormaliz
sage: s3 = polytopes.simplex(3,backend='normaliz')              # optional - pynormaliz
sage: [s1.h_star_vector(),s2.h_star_vector(),s3.h_star_vector()]  # optional - pynormaliz
[[1], [1], [1]]

For a less trivial example, we compute the \(h^*\)-vector of the \(0/1\)-cube, which has the Eulerian numbers \((3,i)\) for \(i \in [0,2]\) as an \(h^*\)-vector:

sage: cube = polytopes.cube(intervals='zero_one', backend='normaliz') # optional - pynormaliz
sage: cube.h_star_vector()   # optional - pynormaliz
[1, 4, 1]
sage: from sage.combinat.combinat import eulerian_number
sage: [eulerian_number(3,i) for i in range(3)]
[1, 4, 1]

hasse_diagram()¶

Return the Hasse diagram of the face lattice of self.

This is the Hasse diagram of the poset of the faces of self.

OUTPUT: a directed graph

EXAMPLES:

sage: P = polytopes.regular_polygon(4).pyramid()
sage: D = P.hasse_diagram(); D
Digraph on 20 vertices
sage: D.degree_polynomial()
x^5 + x^4*y + x*y^4 + y^5 + 4*x^3*y + 8*x^2*y^2 + 4*x*y^3

Faces of an mutable polyhedron are not hashable. Hence those are not suitable as vertices of the hasse diagram. Use the combinatorial polyhedron instead:

sage: P = polytopes.regular_polygon(4).pyramid()
sage: parent = P.parent()
sage: parent = parent.change_ring(QQ, backend='ppl')
sage: Q = parent._element_constructor_(P, mutable=True)
sage: Q.hasse_diagram()
Traceback (most recent call last):
...
TypeError: mutable polyhedra are unhashable
sage: C = Q.combinatorial_polyhedron()
sage: D = C.hasse_diagram()
sage: set(D.vertices()) == set(range(20))
True
sage: def index_to_combinatorial_face(n):
....:     return C.face_by_face_lattice_index(n)
sage: D.relabel(index_to_combinatorial_face, inplace=True)
sage: D.vertices()
[A -1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 0-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 1-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 2-dimensional face of a 3-dimensional combinatorial polyhedron,
 A 3-dimensional face of a 3-dimensional combinatorial polyhedron]
sage: D.degree_polynomial()
x^5 + x^4*y + x*y^4 + y^5 + 4*x^3*y + 8*x^2*y^2 + 4*x*y^3

hyperplane_arrangement()¶

Return the hyperplane arrangement defined by the equations and inequalities.

OUTPUT:

A hyperplane arrangement consisting of the hyperplanes defined by the Hrepresentation(). If the polytope is full-dimensional, this is the hyperplane arrangement spanned by the facets of the polyhedron.

EXAMPLES:

sage: p = polytopes.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 order Vrepresentation().

See also

slack_matrix().

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

The incidence matrix depends on the ambient dimension:

sage: simplex = polytopes.simplex(); simplex
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices
sage: simplex.incidence_matrix()
[1 1 1 1 0]
[1 1 1 0 1]
[1 1 0 1 1]
[1 0 1 1 1]
sage: simplex = simplex.affine_hull_projection(); simplex
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: simplex.incidence_matrix()
[1 1 1 0]
[1 1 0 1]
[1 0 1 1]
[0 1 1 1]

An incidence matrix does not determine a unique polyhedron:

sage: P = Polyhedron(vertices=[[0,1],[1,1],[1,0]])
sage: P.incidence_matrix()
[1 1 0]
[1 0 1]
[0 1 1]

sage: Q = Polyhedron(vertices=[[0,1], [1,0]], rays=[[1,1]])
sage: Q.incidence_matrix()
[1 1 0]
[1 0 1]
[0 1 1]

An example of two polyhedra with isomorphic face lattices but different incidence matrices:

sage: Q.incidence_matrix()
[1 1 0]
[1 0 1]
[0 1 1]

sage: R = Polyhedron(vertices=[[0,1], [1,0]], rays=[[1,3/2], [3/2,1]])
sage: R.incidence_matrix()
[1 1 0]
[1 0 1]
[0 1 0]
[0 0 1]

The incidence matrix has base ring integers. This way one can express various counting questions:

sage: P = polytopes.twenty_four_cell()
sage: M = P.incidence_matrix()
sage: sum(sum(x) for x in M) == P.flag_f_vector(0,3)
True

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() or inequality_generator() instead to iterate over the list of Inequality objects.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,0],[0,0,1],[0,1,0],[1,0,0],[2,2,2]])
sage: p.inequalities_list()[0:3]
[[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: ieqs = p3.inequalities_list()
sage: ieqs[0]
[-6, 0, 1, 1, 1]
sage: ieqs[-1]
[-3, 0, 1, 0, 1]
sage: ieqs == [list(x) for x in p3.inequality_generator()]
True

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 full-dimensional:

sage: simplex = Polyhedron([(1,2,3,5), (2,3,7,5), (-2,-3,-11,5)])
sage: simplex.integral_points()
((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))

sage: point = Polyhedron([(2,3,7)])
sage: point.integral_points()
((2, 3, 7),)

sage: empty = Polyhedron()
sage: empty.integral_points()
()

Here is a simplex where the naive algorithm of running over all points in a rectangular bounding box no longer works fast enough:

sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
sage: simplex = Polyhedron(v); simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices
sage: len(simplex.integral_points())
49

A case where rounding in the right direction goes a long way:

sage: P = 1/10*polytopes.hypercube(14, backend='field')
sage: P.integral_points()
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)

Finally, the 3-d reflexive polytope number 4078:

sage: v = [(1,0,0), (0,1,0), (0,0,1), (0,0,-1), (0,-2,1),
....:      (-1,2,-1), (-1,2,-2), (-1,1,-2), (-1,-1,2), (-1,-3,2)]
sage: P = Polyhedron(v)
sage: pts1 = P.integral_points()                     # Sage's own code
sage: all(P.contains(p) for p in pts1)
True
sage: pts2 = LatticePolytope(v).points()          # 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(function, measure='ambient', **kwds)¶

Return the integral of function over this polytope.

INPUT:

self – Polyhedron
function – a multivariate polynomial or a valid LattE description string for polynomials
measure – string, the measure to use

Allowed values are:
- ambient (default): Lebesgue measure of ambient space,
- induced: Lebesgue measure of the affine hull,
- induced_nonnormalized: Lebesgue measure of the affine hull without the normalization by \(\sqrt{\det(A^\top A)}\) (with \(A\) being the affine transformation matrix; see affine_hull()).
**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 full-dimensional polytope:

sage: x, y = polygens(QQ, 'x, y')
sage: P = Polyhedron(vertices=[[0,0],[1,1]])
sage: P.integrate(x*y)    # optional - latte_int
0
sage: ixy = P.integrate(x*y, measure='induced'); ixy    # optional - latte_int
0.4714045207910317?
sage: ixy.parent()                                      # optional - latte_int
Algebraic Real Field

Convert to a symbolic expression:

sage: ixy.radical_expression()                          # optional - latte_int
1/3*sqrt(2)

Another non full-dimensional polytope integration:

sage: R.<x, y, z> = QQ[]
sage: P = polytopes.simplex(2)
sage: V = AA(P.volume(measure='induced')); V.radical_expression()
1/2*sqrt(3)
sage: P.integrate(R(1), measure='induced') == V                      # optional - latte_int
True

Computing the mass center:

sage: (P.integrate(x, measure='induced') / V).radical_expression()   # optional - latte_int
1/3
sage: (P.integrate(y, measure='induced') / V).radical_expression()   # optional - latte_int
1/3
sage: (P.integrate(z, measure='induced') / V).radical_expression()   # optional - latte_int
1/3

interior()¶

The interior of self.

OUTPUT:

either an empty polyhedron or an instance of RelativeInterior

EXAMPLES:

If the polyhedron is full-dimensional, the result is the same as that of relative_interior():

sage: P_full = Polyhedron(vertices=[[0,0],[1,1],[1,-1]])
sage: P_full.interior()
Relative interior of
 a 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices

If the polyhedron is of strictly smaller dimension than the ambient space, its interior is empty:

sage: P_lower = Polyhedron(vertices=[[0,1], [0,-1]])
sage: P_lower.interior()
The empty polyhedron in ZZ^2

interior_contains(point)¶

Test whether the interior of the polyhedron contains the given point.

INPUT:

point – coordinates of a point

OUTPUT:

True or False.

EXAMPLES:

sage: P = Polyhedron(vertices=[[0,0],[1,1],[1,-1]])
sage: P.contains( [1,0] )
True
sage: P.interior_contains( [1,0] )
False

If the polyhedron is of strictly smaller dimension than the ambient space, its interior is empty:

sage: P = Polyhedron(vertices=[[0,1],[0,-1]])
sage: P.contains( [0,0] )
True
sage: P.interior_contains( [0,0] )
False

The empty polyhedron needs extra care, see trac 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 – a Polyhedron

OUTPUT:

The intersection.

Note that the intersection of two \(\ZZ\)-polyhedra might not be a \(\ZZ\)-polyhedron. In this case, a \(\QQ\)-polyhedron is returned.

EXAMPLES:

sage: cube = polytopes.hypercube(3)
sage: oct = polytopes.cross_polytope(3)
sage: cube.intersection(oct*2)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices

As a shorthand, one may use:

sage: cube & oct*2
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices

The intersection of two \(\ZZ\)-polyhedra is not necessarily a \(\ZZ\)-polyhedron:

sage: P = Polyhedron([(0,0),(1,1)], base_ring=ZZ)
sage: P.intersection(P)
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: Q = Polyhedron([(0,1),(1,0)], base_ring=ZZ)
sage: P.intersection(Q)
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex
sage: _.Vrepresentation()
(A vertex at (1/2, 1/2),)

is_bipyramid(certificate=False)¶

Test whether the polytope is combinatorially equivalent to a bipyramid over some polytope.

INPUT:

certificate – boolean (default: False); specifies whether to return two vertices of the polytope which are the apices of a bipyramid, if found

OUTPUT:

If certificate is True, returns a tuple containing:

Boolean.
None or a tuple containing:
1. The first apex.
2. The second apex.

If certificate is False returns a boolean.

EXAMPLES:

sage: P = polytopes.octahedron()
sage: P.is_bipyramid()
True
sage: P.is_bipyramid(certificate=True)
(True, [A vertex at (-1, 0, 0), A vertex at (1, 0, 0)])
sage: Q = polytopes.cyclic_polytope(3,7)
sage: Q.is_bipyramid()
False
sage: R = Q.bipyramid()
sage: R.is_bipyramid(certificate=True)
(True, [A vertex at (-1, 3, 13, 63), A vertex at (1, 3, 13, 63)])

ALGORITHM:

Assume all faces of a polyhedron to be given as lists of vertices.

A polytope is a bipyramid with apexes \(v\), \(w\) if and only if for each proper face \(v \in F\) there exists a face \(G\) with \(G \setminus \{w\} = F \setminus \{v\}\) and vice versa (for each proper face \(w \in F\) there exists …).

To check this property it suffices to check for all facets of the polyhedron.

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 face lattices are isomorphic.

INPUT:

other – a polyhedron object
algorithm (default = bipartite_graph) – the algorithm to use. The other possible value is face_lattice.

OUTPUT:

True if the two polyhedra are combinatorially isomorphic
False otherwise

REFERENCES:

For the equivalence of the two algorithms see [KK1995], p. 877-878

EXAMPLES:

The square is combinatorially isomorphic to the 2-dimensional cube:

sage: polytopes.hypercube(2).is_combinatorially_isomorphic(polytopes.regular_polygon(4))
True

All the faces of the 3-dimensional 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)[3])
sage: S = S.face_truncation(S.faces(0)[4])
sage: S = S.face_truncation(S.faces(0)[5])
sage: T = polytopes.simplex(3)
sage: T = T.face_truncation(T.faces(0)[3])
sage: T = T.face_truncation(T.faces(0)[4])
sage: T = T.face_truncation(T.faces(0)[4])
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 3-dimensional 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 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: P.is_empty(), P.is_universe()
(False, False)

sage: Q = Polyhedron(vertices=());  Q
The empty polyhedron in ZZ^0
sage: Q.is_empty(), Q.is_universe()
(True, False)

sage: R = Polyhedron(lines=[(1,0),(0,1)]);  R
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines
sage: R.is_empty(), R.is_universe()
(False, True)

is_immutable()¶

Return True if the polyhedron is immutable, i.e. it cannot be modified in place.

EXAMPLES:

sage: p = polytopes.cube(backend='field')
sage: p.is_immutable()
True

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 full-dimensional. A full-dimensional 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 full-dimensional 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 non-full-dimensional 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 full-dimensional polyhedra 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 polyhedra

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

Return True if self is a Lawrence polytope.

A polytope is called a Lawrence polytope if it has a centrally symmetric (normalized) Gale diagram.

EXAMPLES:

sage: P = polytopes.hypersimplex(5,2)
sage: L = P.lawrence_polytope()
sage: L.is_lattice_polytope()
True
sage: egyptian_pyramid = polytopes.regular_polygon(4).pyramid()
sage: egyptian_pyramid.is_lawrence_polytope()
True
sage: polytopes.octahedron().is_lawrence_polytope()
False

REFERENCES:

For more information, see [BaSt1990].

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

Return True if the polyhedron is mutable, i.e. it can be modified in place.

EXAMPLES:

sage: p = polytopes.cube(backend='field')
sage: p.is_mutable()
False

is_neighborly(k=None)¶

Return whether the polyhedron is neighborly.

If the input k is provided, then return whether the polyhedron is k-neighborly

A polyhedron is neighborly if every set of \(n\) vertices forms a face for \(n\) up to floor of half the dimension of the polyhedron. It is \(k\)-neighborly if this is true for \(n\) up to \(k\).

INPUT:

k – the dimension up to which to check if every set of k vertices forms a face. If no k is provided, check up to floor of half the dimension of the polyhedron.

OUTPUT:

True if every set of up to k vertices forms a face,
False otherwise

See also

neighborliness()

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_prism(certificate=False)¶

Test whether the polytope is combinatorially equivalent to a prism of some polytope.

INPUT:

certificate – boolean (default: False); specifies whether to return two facets of the polytope which are the bases of a prism, if found

OUTPUT:

If certificate is True, returns a tuple containing:

Boolean.
None or a tuple containing:
1. List of the vertices of the first base facet.
2. List of the vertices of the second base facet.

If certificate is False returns a boolean.

EXAMPLES:

sage: P = polytopes.cube()
sage: P.is_prism()
True
sage: P.is_prism(certificate=True)
(True,
 [[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)]])
sage: Q = polytopes.cyclic_polytope(3,8)
sage: Q.is_prism()
False
sage: R = Q.prism()
sage: R.is_prism(certificate=True)
(True,
 [[A vertex at (1, 6, 36, 216),
   A vertex at (1, 0, 0, 0),
   A vertex at (1, 7, 49, 343),
   A vertex at (1, 5, 25, 125),
   A vertex at (1, 1, 1, 1),
   A vertex at (1, 2, 4, 8),
   A vertex at (1, 4, 16, 64),
   A vertex at (1, 3, 9, 27)],
  [A vertex at (0, 3, 9, 27),
   A vertex at (0, 6, 36, 216),
   A vertex at (0, 0, 0, 0),
   A vertex at (0, 7, 49, 343),
   A vertex at (0, 5, 25, 125),
   A vertex at (0, 1, 1, 1),
   A vertex at (0, 2, 4, 8),
   A vertex at (0, 4, 16, 64)]])

ALGORITHM:

See Polyhedron_base.is_bipyramid().

is_pyramid(certificate=False)¶

Test whether the polytope is a pyramid over one of its facets.

INPUT:

certificate – boolean (default: False); specifies whether to return a vertex of the polytope which is the apex of a pyramid, if found

OUTPUT:

If certificate is True, returns a tuple containing:

Boolean.
The apex of the pyramid or None.

If certificate is False returns a boolean.

EXAMPLES:

sage: P = polytopes.simplex(3)
sage: P.is_pyramid()
True
sage: P.is_pyramid(certificate=True)
(True, A vertex at (1, 0, 0, 0))
sage: egyptian_pyramid = polytopes.regular_polygon(4).pyramid()
sage: egyptian_pyramid.is_pyramid()
True
sage: Q = polytopes.octahedron()
sage: Q.is_pyramid()
False

For the \(0\)-dimensional polyhedron, the output is True, but it cannot be constructed as a pyramid over the empty polyhedron:

sage: P = Polyhedron([[0]])
sage: P.is_pyramid()
True
sage: Polyhedron().pyramid()
Traceback (most recent call last):
...
ZeroDivisionError: rational division by zero

is_relatively_open()¶

Return whether self is relatively open.

OUTPUT:

Boolean.

EXAMPLES:

sage: P = Polyhedron(vertices=[(1,0), (-1,0)]); P
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: P.is_relatively_open()
False

sage: P0 = Polyhedron(vertices=[[1, 2]]); P0
A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex
sage: P0.is_relatively_open()
True

sage: Empty = Polyhedron(ambient_dim=2); Empty
The empty polyhedron in ZZ^2
sage: Empty.is_relatively_open()
True

sage: Line = Polyhedron(vertices=[(1, 1)], lines=[(1, 0)]); Line
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 line
sage: Line.is_relatively_open()
True

is_self_dual()¶

Return whether the polytope is self-dual.

A polytope is self-dual if its face lattice is isomorphic to the face lattice of its dual polytope.

EXAMPLES:

sage: polytopes.simplex().is_self_dual()
True
sage: polytopes.twenty_four_cell().is_self_dual()
True
sage: polytopes.cube().is_self_dual()
False
sage: polytopes.hypersimplex(5,2).is_self_dual()
False
sage: P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]]).is_self_dual()
Traceback (most recent call last):
...
ValueError: polyhedron has to be compact

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.

A simplex is a bounded polyhedron with \(d+1\) vertices, where \(d\) is the dimension.

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
sage: P = polytopes.simplex(); P
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices
sage: P.is_simplicial()
True

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 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices
sage: P.is_empty(), P.is_universe()
(False, False)

sage: Q = Polyhedron(vertices=());  Q
The empty polyhedron in ZZ^0
sage: Q.is_empty(), Q.is_universe()
(True, False)

sage: R = Polyhedron(lines=[(1,0),(0,1)]);  R
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 lines
sage: R.is_empty(), R.is_universe()
(False, True)

join(other)¶

Return the join of self and other.

The join of two polyhedra is obtained by first placing the two objects in two non-intersecting 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 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
sage: P1.join(P1)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: P2.join(P2)
A 3-dimensional 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 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 2 vertices and 2 rays

join_of_Vrep(*Vrepresentatives)¶

Return the smallest face that contains Vrepresentatives.

INPUT:

Vrepresentatives – vertices/rays/lines of self or indices of such

OUTPUT: a PolyhedronFace

Note

In the case of unbounded polyhedra, the join of rays etc. may not be well-defined.

EXAMPLES:

sage: P = polytopes.permutahedron(5)
sage: P.join_of_Vrep(1)
A 0-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 1 vertex
sage: P.join_of_Vrep()
A -1-dimensional face of a Polyhedron in ZZ^5
sage: P.join_of_Vrep(0,12,13).ambient_V_indices()
(0, 12, 13, 68)

The input is flexible:

sage: P.join_of_Vrep(2, P.vertices()[3], P.Vrepresentation(4))
A 2-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 6 vertices

sage: P = polytopes.cube()
sage: a, b = P.faces(0)[:2]
sage: P.join_of_Vrep(a, b)
A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices

In the case of an unbounded polyhedron, the join may not be well-defined:

sage: P = Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,1]])
sage: P.join_of_Vrep(0)
A 0-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex
sage: P.join_of_Vrep(0,1)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.join_of_Vrep(0,2)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray
sage: P.join_of_Vrep(1,2)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray
sage: P.join_of_Vrep(2)
Traceback (most recent call last):
...
ValueError: the join is not well-defined

The Vrepresentatives must be of self:

sage: P = polytopes.cube(backend='ppl')
sage: Q = polytopes.cube(backend='field')
sage: v = P.vertices()[0]
sage: P.join_of_Vrep(v)
A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex
sage: Q.join_of_Vrep(v)
Traceback (most recent call last):
...
ValueError: not a Vrepresentative of ``self``
sage: f = P.faces(0)[0]
sage: P.join_of_Vrep(v)
A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex
sage: Q.join_of_Vrep(v)
Traceback (most recent call last):
...
ValueError: not a Vrepresentative of ``self``

lattice_polytope(envelope=False)¶

Return an encompassing lattice polytope.

INPUT:

envelope – boolean (default: False). If the polyhedron has non-integral vertices, this option decides whether to return a strictly larger lattice polytope or raise a ValueError. 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 non-integral vertex, a strictly larger lattice polytope is returned.

If the polyhedron is not compact, a NotImplementedError is raised.

If the polyhedron is not integral and envelope=False, a ValueError is raised.

ALGORITHM:

For each non-integral vertex, a bounding box of integral points is added and the convex hull of these integral points is returned.

EXAMPLES:

First, a polyhedron with integral vertices:

sage: P = Polyhedron( vertices = [(1, 0), (0, 1), (-1, 0), (0, -1)])
sage: lp = P.lattice_polytope(); lp
2-d reflexive polytope #3 in 2-d lattice M
sage: lp.vertices()
M(-1,  0),
M( 0, -1),
M( 0,  1),
M( 1,  0)
in 2-d lattice M

Here is a polyhedron with non-integral vertices:

sage: P = Polyhedron( vertices = [(1/2, 1/2), (0, 1), (-1, 0), (0, -1)])
sage: lp = P.lattice_polytope()
Traceback (most recent call last):
...
ValueError: Some vertices are not integral. You probably want
to add the argument "envelope=True" to compute an enveloping
lattice polytope.
sage: lp = P.lattice_polytope(True); lp
2-d reflexive polytope #5 in 2-d lattice M
sage: lp.vertices()
M(-1,  0),
M( 0, -1),
M( 1,  1),
M( 0,  1),
M( 1,  0)
in 2-d lattice M

lawrence_extension(v)¶

Return the Lawrence extension of self on the point v.

Let \(P\) be a polytope and \(v\) be a vertex of \(P\) or a point outside \(P\). The Lawrence extension of \(P\) on \(v\) is the convex hull of \((v,1),(v,2)\) and \((u,0)\) for all vertices \(u\) in \(P\) other than \(v\) if \(v\) is a vertex.

INPUT:

v – a vertex of self or a point outside it

EXAMPLES:

sage: P = polytopes.cube()
sage: P.lawrence_extension(P.vertices()[0])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 9 vertices
sage: P.lawrence_extension([-1,-1,-1])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 9 vertices

REFERENCES:

For more information, see Section 6.6 of [Zie2007].

lawrence_polytope()¶

Return the Lawrence polytope of self.

Let \(P\) be a \(d\)-polytope in \(\RR^r\) with \(n\) vertices. The Lawrence polytope of \(P\) is the polytope whose vertices are the columns of the following \((r+n)\)-by-\(2n\) matrix.

\[\begin{split}\begin{pmatrix} V & V \\ I_n & 2I_n \end{pmatrix},\end{split}\]

where \(V\) is the \(r\)-by-\(n\) vertices matrix of \(P\).

EXAMPLES:

sage: P = polytopes.octahedron()
sage: L = P.lawrence_polytope(); L
A 9-dimensional polyhedron in ZZ^9 defined as the convex hull of 12 vertices
sage: V = P.vertices_list()
sage: i = 0
sage: for v in V:
....:     v = v + i*[0]
....:     P = P.lawrence_extension(v)
....:     i = i + 1
sage: P == L
True

REFERENCES:

For more information, see Section 6.6 of [Zie2007].

least_common_superface_of_Vrep(*Vrepresentatives)¶

Return the smallest face that contains Vrepresentatives.

INPUT:

Vrepresentatives – vertices/rays/lines of self or indices of such

OUTPUT: a PolyhedronFace

Note

In the case of unbounded polyhedra, the join of rays etc. may not be well-defined.

EXAMPLES:

sage: P = polytopes.permutahedron(5)
sage: P.join_of_Vrep(1)
A 0-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 1 vertex
sage: P.join_of_Vrep()
A -1-dimensional face of a Polyhedron in ZZ^5
sage: P.join_of_Vrep(0,12,13).ambient_V_indices()
(0, 12, 13, 68)

The input is flexible:

sage: P.join_of_Vrep(2, P.vertices()[3], P.Vrepresentation(4))
A 2-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 6 vertices

sage: P = polytopes.cube()
sage: a, b = P.faces(0)[:2]
sage: P.join_of_Vrep(a, b)
A 1-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 2 vertices

In the case of an unbounded polyhedron, the join may not be well-defined:

sage: P = Polyhedron(vertices=[[1,0], [0,1]], rays=[[1,1]])
sage: P.join_of_Vrep(0)
A 0-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex
sage: P.join_of_Vrep(0,1)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.join_of_Vrep(0,2)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray
sage: P.join_of_Vrep(1,2)
A 1-dimensional face of a Polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray
sage: P.join_of_Vrep(2)
Traceback (most recent call last):
...
ValueError: the join is not well-defined

The Vrepresentatives must be of self:

sage: P = polytopes.cube(backend='ppl')
sage: Q = polytopes.cube(backend='field')
sage: v = P.vertices()[0]
sage: P.join_of_Vrep(v)
A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex
sage: Q.join_of_Vrep(v)
Traceback (most recent call last):
...
ValueError: not a Vrepresentative of ``self``
sage: f = P.faces(0)[0]
sage: P.join_of_Vrep(v)
A 0-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 1 vertex
sage: Q.join_of_Vrep(v)
Traceback (most recent call last):
...
ValueError: not a Vrepresentative of ``self``

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)

linear_transformation(linear_transf, new_base_ring=None)¶

Return the linear transformation of self.

INPUT:

linear_transf – a matrix, not necessarily in base_ring()
new_base_ring – ring (optional); specify the new base ring; may avoid coercion failure

OUTPUT:

The polyhedron transformed by that matrix, possibly coerced to a bigger base ring.

EXAMPLES:

sage: b3 = polytopes.Birkhoff_polytope(3)
sage: proj_mat=matrix([[0,1,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0],[0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,1,0]])
sage: b3_proj = proj_mat * b3; b3_proj
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices

sage: square = polytopes.regular_polygon(4)
sage: square.vertices_list()
[[0, -1], [1, 0], [-1, 0], [0, 1]]
sage: transf = matrix([[1,1],[0,1]])
sage: sheared = transf * square
sage: sheared.vertices_list()
[[-1, -1], [1, 0], [-1, 0], [1, 1]]
sage: sheared == square.linear_transformation(transf)
True

Specifying the new base ring may avoid coercion failure:

sage: K.<sqrt2> = QuadraticField(2)
sage: L.<sqrt3> = QuadraticField(3)
sage: P = polytopes.cube()*sqrt2
sage: M = matrix([[sqrt3, 0, 0], [0, sqrt3, 0], [0, 0, 1]])
sage: P.linear_transformation(M, new_base_ring=K.composite_fields(L)[0])
A 3-dimensional polyhedron in (Number Field in sqrt2sqrt3 with defining polynomial x^4 - 10*x^2 + 1 with sqrt2sqrt3 = 0.3178372451957823?)^3 defined as the convex hull of 8 vertices

Linear transformation without specified new base ring fails in this case:

sage: M*P
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for *: 'Full MatrixSpace of 3 by 3 dense matrices over Number Field in sqrt3 with defining polynomial x^2 - 3 with sqrt3 = 1.732050807568878?' and 'Full MatrixSpace of 3 by 8 dense matrices over Number Field in sqrt2 with defining polynomial x^2 - 2 with sqrt2 = 1.414213562373095?'

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 of Line objects.

EXAMPLES:

sage: p = Polyhedron(rays = [[1,0],[-1,0],[0,1],[1,1]], vertices = [[-2,-2],[2,3]])
sage: p.lines_list()
[[1, 0]]
sage: p.lines_list() == [list(x) for x in p.line_generator()]
True

meet_of_Hrep(*Hrepresentatives)¶

Return the largest face that is contained in Hrepresentatives.

INPUT:

Hrepresentatives – facets or indices of Hrepresentatives; the indices are assumed to be the indices of the Hrepresentation

OUTPUT: a PolyhedronFace

EXAMPLES:

sage: P = polytopes.permutahedron(5)
sage: P.meet_of_Hrep()
A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 120 vertices
sage: P.meet_of_Hrep(1)
A 3-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 24 vertices
sage: P.meet_of_Hrep(4)
A 3-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 12 vertices
sage: P.meet_of_Hrep(1,3,7)
A 1-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 2 vertices
sage: P.meet_of_Hrep(1,3,7).ambient_H_indices()
(0, 1, 3, 7)

The indices are the indices of the Hrepresentation. 0 corresponds to an equation and is ignored:

sage: P.meet_of_Hrep(0)
A 4-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 120 vertices

The input is flexible:

sage: P.meet_of_Hrep(P.facets()[-1], P.inequalities()[2], 7)
A 1-dimensional face of a Polyhedron in ZZ^5 defined as the convex hull of 2 vertices

The Hrepresentatives must belong to self:

sage: P = polytopes.cube(backend='ppl')
sage: Q = polytopes.cube(backend='field')
sage: f = P.facets()[0]
sage: P.meet_of_Hrep(f)
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: Q.meet_of_Hrep(f)
Traceback (most recent call last):
...
ValueError: not a facet of ``self``
sage: f = P.inequalities()[0]
sage: P.meet_of_Hrep(f)
A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: Q.meet_of_Hrep(f)
Traceback (most recent call last):
...
ValueError: not a facet of ``self``

minkowski_difference(other)¶

Return the Minkowski difference.

Minkowski subtraction can equivalently be defined via Minkowski addition (see minkowski_sum()) or as set-theoretic intersection via

\[X \ominus Y = (X^c \oplus Y)^c = \cap_{y\in Y} (X-y)\]

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\).
\((X-Y)+Y \subseteq X\)
\((X-Y)+Y = X\) if and only if Y is a Minkowski summand of X.

INPUT:

other – a Polyhedron_base

OUTPUT:

The Minkowski difference of self and other. Also known as Minkowski subtraction of other from self.

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: (X-Y)+Y < X
True

The polyhedra need not be full-dimensional:

sage: X2 = Polyhedron(vertices=[(-1,-1,0),(1,-1,0),(-1,1,0),(1,1,0)])
sage: Y2 = Polyhedron(vertices=[(0,0,0), (0,1,0), (1,0,0)]) / 2
sage: (X2+Y2)-Y2 == X2
True
sage: (X2-Y2)+Y2 < X2
True

Minus sign is really an alias for minkowski_difference()

sage: four_cube = polytopes.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 4-dimensional polyhedron in QQ^4 defined as the convex hull of 16 vertices
sage: four_cube.minkowski_difference(four_simplex) == four_cube - four_simplex
True

Coercion of the base ring works:

sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ)
sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ) / 100
sage: poly_spam - poly_eggs
A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 5 vertices

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 – a Polyhedron_base

OUTPUT:

The Minkowski sum of self and other

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 3-dimensional 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 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 36 vertices
sage: four_cube.minkowski_sum(four_simplex) == four_cube + four_simplex
True

sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ)
sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ)
sage: poly_spam + poly_spam + poly_eggs
A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 12 vertices

n_Hrepresentation()¶

Return the number of objects that make up the H-representation of the polyhedron.

OUTPUT:

Integer.

EXAMPLES:

sage: p = polytopes.cross_polytope(4)
sage: p.n_Hrepresentation()
16
sage: p.n_Hrepresentation() == p.n_inequalities() + p.n_equations()
True

n_Vrepresentation()¶

Return the number of objects that make up the V-representation 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.

Warning

If the polyhedron has lines, return the number of vertices in the Vrepresentation. As the represented polyhedron has no 0-dimensional faces (i.e. vertices), n_vertices corresponds to the number of \(k\)-faces, where \(k\) is the number of lines:

sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]])
sage: P.n_vertices()
1
sage: P.faces(0)
()
sage: P.f_vector()
(1, 0, 1, 1)

sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0],[0,1,1]])
sage: P.n_vertices()
1
sage: P.f_vector()
(1, 0, 0, 1, 1)

EXAMPLES:

sage: p = Polyhedron(vertices = [[1,0],[0,1],[1,1]], rays=[[1,1]])
sage: p.n_vertices()
2

neighborliness()¶

Return the largest k, such that the polyhedron is k-neighborly.

A polyhedron is \(k\)-neighborly if every set of \(n\) vertices forms a face for \(n\) up to \(k\).

In case of the \(d\)-dimensional simplex, it returns \(d + 1\).

See also

is_neighborly()

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 0-dimensional polyhedron in ZZ^1 defined as the convex hull of 1 vertex
sage: P.neighborliness()
1
sage: S = polytopes.simplex(5); S
A 5-dimensional 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 7-dimensional 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 6-dimensional 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(direction='inner')¶

Return the normal fan of a compact full-dimensional rational polyhedron.

This returns the inner normal fan of self. For the outer normal fan, use direction='outer'.

INPUT:

direction – either 'inner' (default) or 'outer'; if set to 'inner', use the inner normal vectors to span the cones of the fan, if set to 'outer', use the outer normal vectors.

OUTPUT:

A complete fan of the ambient space as a RationalPolyhedralFan.

See also

face_fan().

EXAMPLES:

sage: S = Polyhedron(vertices = [[0, 0], [1, 0], [0, 1]])
sage: S.normal_fan()
Rational polyhedral fan in 2-d lattice N

sage: C = polytopes.hypercube(4)
sage: NF = C.normal_fan(); NF
Rational polyhedral fan in 4-d 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 full-dimensional 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

sage: P = Polyhedron(vertices=[[0,0],[2,0],[0,2],[2,1],[1,2]])
sage: P.normal_fan(direction=None)
Traceback (most recent call last):
...
TypeError: the direction should be 'inner' or 'outer'

sage: inner_nf = P.normal_fan()
sage: inner_nf.rays()
N( 1,  0),
N( 0, -1),
N( 0,  1),
N(-1,  0),
N(-1, -1)
in 2-d lattice N

sage: outer_nf = P.normal_fan(direction='outer')
sage: outer_nf.rays()
N( 1,  0),
N( 1,  1),
N( 0,  1),
N(-1,  0),
N( 0, -1)
in 2-d lattice N

REFERENCES:

For more information, see Chapter 7 of [Zie2007].

one_point_suspension(vertex)¶

Return the one-point suspension of self by splitting the vertex vertex.

The resulting polyhedron has one more vertex and its dimension increases by one.

INPUT:

vertex – a Vertex of self

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)[1]
sage: ops_cube2 = cube.one_point_suspension(vv)
sage: ops_cube == ops_cube2
True

See also

face_split()

plot(point=None, line=None, polygon=None, wireframe='blue', fill='green', position=None, orthonormal=True, **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 to point, line, and polygon, but fill is used for the graphics objects in the dimension of the polytope (or of dimension 2 for higher dimensional polytopes) and wireframe is used for all lower-dimensional graphics objects (default: ‘green’ for fill and ‘blue’ for wireframe)
position – positive number; the position to take the projection point in Schlegel diagrams.
orthonormal – Boolean (default: True); whether to use orthonormal projections.
**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 and wireframe 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

It is possible to draw polyhedra up to dimension 4, no matter what the ambient dimension is:

sage: hcube = polytopes.hypercube(5)
sage: facet = hcube.facets()[0].as_polyhedron();facet
A 4-dimensional polyhedron in ZZ^5 defined as the convex hull of 16 vertices
sage: facet.plot()
Graphics3d Object

polar(in_affine_span=False)¶

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.

The polytope must be full-dimensional, unless in_affine_span is True. If in_affine_span is True, then the operation will be performed in the linear/affine span of the polyhedron (after translation).

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0,1],[0,1,0],[1,0,0],[0,0,0],[1,1,1]], base_ring=QQ)
sage: p
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices
sage: p.polar()
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices

sage: cube = polytopes.hypercube(3)
sage: octahedron = polytopes.cross_polytope(3)
sage: cube_dual = cube.polar()
sage: octahedron == cube_dual
True

in_affine_span somewhat ignores equations, performing the polar in the spanned subspace (after translating barycenter to origin):

sage: P = polytopes.simplex(3, base_ring=QQ)
sage: P.polar(in_affine_span=True)
A 3-dimensional polyhedron in QQ^4 defined as the convex hull of 4 vertices

Embedding the polytope in a higher dimension, commutes with polar in this case:

sage: point = Polyhedron([[0]])
sage: P = polytopes.cube().change_ring(QQ)
sage: (P*point).polar(in_affine_span=True) == P.polar()*point
True

prism()¶

Return a prism of the original polyhedron.

EXAMPLES:

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

product(other)¶

Return the Cartesian product.

INPUT:

other – a Polyhedron_base

OUTPUT:

The Cartesian product of self and other with a suitable base ring to encompass the two.

EXAMPLES:

sage: P1 = Polyhedron([[0],[1]], base_ring=ZZ)
sage: P2 = Polyhedron([[0],[1]], base_ring=QQ)
sage: P1.product(P2)
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices

The Cartesian product is the product in the semiring of polyhedra:

sage: P1 * P1
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: P1 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P2 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: 2 * P1
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices
sage: P1 * 2.0
A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices

An alias is cartesian_product():

sage: P1.cartesian_product(P2) == P1.product(P2)
True

projection(projection=None)¶

Return a projection object.

INPUT:

proj – a projection function

OUTPUT:

The identity projection. This is useful for plotting polyhedra.

See also

schlegel_projection() for a more interesting projection.

EXAMPLES:

sage: p = polytopes.hypercube(3)
sage: proj = p.projection()
sage: proj
The projection of a polyhedron into 3 dimensions

pyramid()¶

Return a polyhedron that is a pyramid over the original.

EXAMPLES:

sage: square = polytopes.hypercube(2);  square
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: egyptian_pyramid = square.pyramid();  egyptian_pyramid
A 3-dimensional polyhedron in 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 to self.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, an EmptySetError is raised.

See also

get_integral_point().

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() or ray_generator() instead to iterate over the list of Ray objects.

OUTPUT:

A list of rays as lists of coordinates.

EXAMPLES:

sage: p = Polyhedron(ieqs = [[0,0,0,1],[0,0,1,0],[1,1,0,0]])
sage: p.rays_list()
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
sage: p.rays_list() == [list(r) for r in p.ray_generator()]
True

relative_interior()¶

Return the relative interior of self.

EXAMPLES:

sage: P = Polyhedron(vertices=[(1,0), (-1,0)])
sage: ri_P = P.relative_interior(); ri_P
Relative interior of
 a 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: (0, 0) in ri_P
True
sage: (1, 0) in ri_P
False

sage: P0 = Polyhedron(vertices=[[1, 2]])
sage: P0.relative_interior() is P0
True

sage: Empty = Polyhedron(ambient_dim=2)
sage: Empty.relative_interior() is Empty
True

sage: Line = Polyhedron(vertices=[(1, 1)], lines=[(1, 0)])
sage: Line.relative_interior() is Line
True

relative_interior_contains(point)¶

Test whether the relative interior of the polyhedron contains the given point.

See also

contains(), interior_contains().

INPUT:

point – coordinates of a point

OUTPUT:

True or False

EXAMPLES:

sage: P = Polyhedron(vertices=[(1,0), (-1,0)])
sage: P.contains( (0,0) )
True
sage: P.interior_contains( (0,0) )
False
sage: P.relative_interior_contains( (0,0) )
True
sage: P.relative_interior_contains( (1,0) )
False

The empty polyhedron needs extra care, see trac 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 3-d 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]

representative_point()¶

Return a “generic” point.

See also

center().

OUTPUT:

A point as a coordinate vector. The point is chosen to be interior as far as possible. If the polyhedron is not full-dimensional, the point is in the relative interior. If the polyhedron is zero-dimensional, its single point is returned.

EXAMPLES:

sage: p = Polyhedron(vertices=[(3,2)], rays=[(1,-1)])
sage: p.representative_point()
(4, 1)
sage: p.center()
(3, 2)

sage: Polyhedron(vertices=[(3,2)]).representative_point()
(3, 2)

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 swapping self.Vrepresentation(0) and self.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" – like matrix, 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" and output="permutation": a PermutationGroup.
For output="matrix": a MatrixGroup.
For output="matrixlist": a list of matrices.

REFERENCES:

[BSS2009]

EXAMPLES:

A cross-polytope 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 fool-proof 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

24-cell 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 full-dimensional:

sage: P = Polyhedron(vertices=[(1,2,3,4,5),(7,8,9,10,11)])
sage: P.restricted_automorphism_group()
Permutation Group with generators [(1,2)]
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 non-degenerate triangle has the dihedral group with 6 elements, \(D_6\), as its automorphism group:

sage: initial_points = [vector([1,0]), vector([0,1]), vector([-2,-1])]
sage: points = initial_points
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - initial_points[0] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - initial_points[1] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]
sage: points = [pt - 2*initial_points[1] for pt in initial_points]
sage: Polyhedron(vertices=points).restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]

The output="matrixlist" can be used over fields without a complete implementation of matrix groups:

sage: P = polytopes.dodecahedron(); P
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^3 defined as the convex hull of 20 vertices
sage: G = P.restricted_automorphism_group(output="matrixlist")
sage: len(G)
120

Floating-point 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(facet=None, position=None)¶

Return the Schlegel projection.

The facet is orthonormally transformed into its affine hull.
The position specifies a point coming out of the barycenter of the facet from which the other vertices will be projected into the facet.

INPUT:

facet – a PolyhedronFace. The facet into which the Schlegel diagram is created. The default is the first facet.
position – a positive number. Determines a relative distance from the barycenter of facet. A value close to 0 will place the projection point close to the facet and a large value further away. Default is \(1\). If the given value is too large, an error is returned.

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])
8

The Schlegel projection preserves the convexity of facets, see trac ticket #30015:

sage: fcube = polytopes.hypercube(4)
sage: tfcube = fcube.face_truncation(fcube.faces(0)[0])
sage: tfcube.facets()[-1]
A 3-dimensional face of a Polyhedron in QQ^4 defined as the convex hull of 8 vertices
sage: sp = tfcube.schlegel_projection(tfcube.facets()[-1])
sage: sp.plot()
Graphics3d Object

The same truncated cube but see inside the tetrahedral facet:

sage: tfcube.facets()[4]
A 3-dimensional face of a Polyhedron in QQ^4 defined as the convex hull of 4 vertices
sage: sp = tfcube.schlegel_projection(tfcube.facets()[4])
sage: sp.plot()
Graphics3d Object

A different values of position changes the projection:

sage: sp = tfcube.schlegel_projection(tfcube.facets()[4],1/2)
sage: sp.plot()
Graphics3d Object
sage: sp = tfcube.schlegel_projection(tfcube.facets()[4],4)
sage: sp.plot()
Graphics3d Object

A value which is too large give a projection point that sees more than one facet resulting in a error:

sage: sp = tfcube.schlegel_projection(tfcube.facets()[4],5)
Traceback (most recent call last):
...
ValueError: the chosen position is too large

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. See plot() 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')

simpliciality()¶

Return the largest integer \(k\) such that the polytope is \(k\)-simplicial.

A polytope is \(k\)-simplicial, if every \(k\)-face is a simplex. If \(self\) is a simplex, returns its dimension.

EXAMPLES:

sage: polytopes.cyclic_polytope(10,4).simpliciality()
3
sage: polytopes.hypersimplex(5,2).simpliciality()
2
sage: polytopes.cross_polytope(4).simpliciality()
3
sage: polytopes.simplex(3).simpliciality()
3
sage: polytopes.simplex(1).simpliciality()
1

The method is not implemented for unbounded polyhedra:

sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
sage: p.simpliciality()
Traceback (most recent call last):
...
NotImplementedError: this function is implemented for polytopes only

simplicity()¶

Return the largest integer \(k\) such that the polytope is \(k\)-simple.

A polytope \(P\) is \(k\)-simple, if every \((d-1-k)\)-face is contained in exactly \(k+1\) facets of \(P\) for \(1 \leq k \leq d-1\). Equivalently it is \(k\)-simple if the polar/dual polytope is \(k\)-simplicial. If \(self\) is a simplex, it returns its dimension.

EXAMPLES:

sage: polytopes.hypersimplex(4,2).simplicity()
1
sage: polytopes.hypersimplex(5,2).simplicity()
2
sage: polytopes.hypersimplex(6,2).simplicity()
3
sage: polytopes.simplex(3).simplicity()
3
sage: polytopes.simplex(1).simplicity()
1

The method is not implemented for unbounded polyhedra:

sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
sage: p.simplicity()
Traceback (most recent call last):
...
NotImplementedError: this function is implemented for polytopes only

slack_matrix()¶

Return the slack matrix.

The entries correspond to the evaluation of the Hrepresentation elements on the Vrepresentation elements.

Note

The columns correspond to inequalities/equations in the order Hrepresentation(), the rows correspond to vertices/rays/lines in the order Vrepresentation().

See also

incidence_matrix().

EXAMPLES:

sage: P = polytopes.cube()
sage: P.slack_matrix()
[0 2 2 2 0 0]
[0 0 2 2 0 2]
[0 0 0 2 2 2]
[0 2 0 2 2 0]
[2 2 0 0 2 0]
[2 2 2 0 0 0]
[2 0 2 0 0 2]
[2 0 0 0 2 2]

sage: P = polytopes.cube(intervals='zero_one')
sage: P.slack_matrix()
[0 1 1 1 0 0]
[0 0 1 1 0 1]
[0 0 0 1 1 1]
[0 1 0 1 1 0]
[1 1 0 0 1 0]
[1 1 1 0 0 0]
[1 0 1 0 0 1]
[1 0 0 0 1 1]

sage: P = polytopes.dodecahedron().faces(2)[0].as_polyhedron()
sage: P.slack_matrix()
[1/2*sqrt5 - 1/2               0               0               1 1/2*sqrt5 - 1/2               0]
[              0               0 1/2*sqrt5 - 1/2 1/2*sqrt5 - 1/2               1               0]
[              0 1/2*sqrt5 - 1/2               1               0 1/2*sqrt5 - 1/2               0]
[              1 1/2*sqrt5 - 1/2               0 1/2*sqrt5 - 1/2               0               0]
[1/2*sqrt5 - 1/2               1 1/2*sqrt5 - 1/2               0               0               0]

sage: P = Polyhedron(rays=[[1, 0], [0, 1]])
sage: P.slack_matrix()
[0 0]
[0 1]
[1 0]

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 number. Determines a relative distance from the barycenter of face. 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.facets()[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: cannot 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)[2]
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

sage: s = polytopes.simplex(7)
sage: f = s.faces(3)[69]
sage: sf = s.stack(f); sf
A 7-dimensional polyhedron in QQ^8 defined as the convex hull of 9 vertices
sage: sf.vertices()
(A vertex at (-4, -4, -4, -4, 17/4, 17/4, 17/4, 17/4),
 A vertex at (0, 0, 0, 0, 0, 0, 0, 1),
 A vertex at (0, 0, 0, 0, 0, 0, 1, 0),
 A vertex at (0, 0, 0, 0, 0, 1, 0, 0),
 A vertex at (0, 0, 0, 0, 1, 0, 0, 0),
 A vertex at (0, 0, 0, 1, 0, 0, 0, 0),
 A vertex at (0, 0, 1, 0, 0, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 0, 0, 0),
 A vertex at (1, 0, 0, 0, 0, 0, 0, 0))

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 (1, 0),
 A ray in the direction (1, 1),
 A vertex at (2, 0))
sage: Q.stack(E[1],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[2],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))

Stacking requires a proper face:

sage: Q.stack(Q.faces(2)[0])
Traceback (most recent call last):
...
ValueError: can only stack on proper face

subdirect_sum(other)¶

Return the subdirect sum of self and other.

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 – a Polyhedron_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 2-dimensional 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

join() direct_sum()

tikz(view=[0, 0, 1], angle=0, scale=1, edge_color='blue!95!black', facet_color='blue!95!black', opacity=0.8, vertex_color='green', axis=False)¶

Return a string tikz_pic consisting of a tikz picture of self according to a projection view and an angle angle obtained via the threejs viewer.

INPUT:

view - list (default: [0,0,1]) representing the rotation axis (see note below).
angle - integer (default: 0) angle of rotation in degree from 0 to 360 (see note below).
scale - integer (default: 1) specifying the scaling of the tikz picture.
edge_color - string (default: ‘blue!95!black’) representing colors which tikz recognize.
facet_color - string (default: ‘blue!95!black’) representing colors which tikz recognize.
vertex_color - string (default: ‘green’) representing colors which tikz recognize.
opacity - real number (default: 0.8) between 0 and 1 giving the opacity of the front facets.
axis - Boolean (default: False) draw the axes at the origin or not.

OUTPUT:

LatexExpr – containing the TikZ picture.

Note

This is a wrapper of a method of the projection object \(self.projection()\). See tikz() for more detail.

The inputs view and angle can be obtained by visualizing it using .show(aspect_ratio=1). This will open an interactive view in your default browser, where you can rotate the polytope. Once the desired view angle is found, click on the information icon in the lower right-hand corner and select Get Viewpoint. This will copy a string of the form ‘[x,y,z],angle’ to your local clipboard. Go back to Sage and type Img = P.tikz([x,y,z],angle).

The inputs view and angle can also be obtained from the viewer Jmol:

1) Right click on the image
2) Select ``Console``
3) Select the tab ``State``
4) Scroll to the line ``moveto``

It reads something like:

moveto 0.0 {x y z angle} Scale

The view is then [x,y,z] and angle is angle. The following number is the scale.

Jmol performs a rotation of angle degrees along the vector [x,y,z] and show the result from the z-axis.

EXAMPLES:

sage: co = polytopes.cuboctahedron()
sage: Img = co.tikz([0,0,1], 0)
sage: print('\n'.join(Img.splitlines()[:9]))
\begin{tikzpicture}%
    [x={(1.000000cm, 0.000000cm)},
    y={(0.000000cm, 1.000000cm)},
    z={(0.000000cm, 0.000000cm)},
    scale=1.000000,
    back/.style={loosely dotted, thin},
    edge/.style={color=blue!95!black, thick},
    facet/.style={fill=blue!95!black,fill opacity=0.800000},
    vertex/.style={inner sep=1pt,circle,draw=green!25!black,fill=green!75!black,thick}]
sage: print('\n'.join(Img.splitlines()[12:21]))
%% with the command: ._tikz_3d_in_3d and parameters:
%% view = [0, 0, 1]
%% angle = 0
%% scale = 1
%% edge_color = blue!95!black
%% facet_color = blue!95!black
%% opacity = 0.8
%% vertex_color = green
%% axis = False
sage: print('\n'.join(Img.splitlines()[22:26]))
%% Coordinate of the vertices:
%%
\coordinate (-1.00000, -1.00000, 0.00000) at (-1.00000, -1.00000, 0.00000);
\coordinate (-1.00000, 0.00000, -1.00000) at (-1.00000, 0.00000, -1.00000);

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 for MixedIntegerLinearProgram. Set to None by default.
return_variable – (default: False) If True, return a tuple (p, x), where p is the MixedIntegerLinearProgram object and x is the vector-valued MIP variable in this problem, indexed from 0. If False, only return p.
base_ring – select a field over which the linear program should be set up. Use RDF to request a fast inexact (floating point) solver even if self 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 a MixedIntegerLinearProgram 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]

Floating-point 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 1e-5
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 1e-8
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 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
sage: P.translation( vector(QQ,[2,1]) )
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices

triangulate(engine='auto', connected=True, fine=False, regular=None, star=None)¶

Return a triangulation of the polytope.

INPUT:

engine – either ‘auto’ (default), ‘internal’, ‘TOPCOM’, or ‘normaliz’. The ‘internal’ and ‘TOPCOM’ 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 or None (default: None). Whether the triangulations must be regular. A regular triangulation is one that is induced by a piecewise-linear convex support function. In other words, the shadows of the faces of a polyhedron in one higher dimension.
- True: Only regular triangulations.
- False: Only non-regular triangulations.
- None (default): Both kinds of triangulation.
star – either None (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 the Vrepresentation() 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,5,7>, <0,2,3,7>, <0,3,4,7>, <0,4,5,7>, <1,5,6,7>)
sage: simplex_indices = triangulation[0]; simplex_indices
(0, 1, 2, 7)
sage: simplex_vertices = [ cube.Vrepresentation(i) for i in simplex_indices ]
sage: simplex_vertices
[A vertex at (1, -1, -1),
 A vertex at (1, 1, -1),
 A vertex at (1, 1, 1),
 A vertex at (-1, 1, 1)]
sage: Polyhedron(simplex_vertices)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices

It is possible to use 'normaliz' as an engine. For this, the polyhedron should have the backend set to normaliz:

sage: P = Polyhedron(vertices=[[0,0,1],[1,0,1],[0,1,1],[1,1,1]],backend='normaliz')  # optional - pynormaliz
sage: P.triangulate(engine='normaliz')  # optional - pynormaliz
(<0,1,2>, <1,2,3>)

sage: P = Polyhedron(vertices=[[0,0,1],[1,0,1],[0,1,1],[1,1,1]])
sage: P.triangulate(engine='normaliz')
Traceback (most recent call last):
...
TypeError: the polyhedron's backend should be 'normaliz'

The normaliz engine can triangulate pointed cones:

sage: C1 = Polyhedron(rays=[[0,0,1],[1,0,1],[0,1,1],[1,1,1]],backend='normaliz')  # optional - pynormaliz
sage: C1.triangulate(engine='normaliz')  # optional - pynormaliz
(<0,1,2>, <1,2,3>)
sage: C2 = Polyhedron(rays=[[1,0,1],[0,0,1],[0,1,1],[1,1,10/9]],backend='normaliz')  # optional - pynormaliz
sage: C2.triangulate(engine='normaliz')  # optional - pynormaliz
(<0,1,2>, <1,2,3>)

They can also be affine cones:

sage: K = Polyhedron(vertices=[[1,1,1]],rays=[[1,0,0],[0,1,0],[1,1,-1],[1,1,1]], backend='normaliz')  # optional - pynormaliz
sage: K.triangulate(engine='normaliz')  # optional - pynormaliz
(<0,1,2>, <0,1,3>)

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]

Two vertices can bound a finite-length edge.
A vertex and a ray can generate a half-infinite 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 half-plane:

sage: half_plane = Polyhedron(ieqs=[(0,1,0)])
sage: half_plane.Hrepresentation()
(An inequality (1, 0) x + 0 >= 0,)

Its (non-unique) V-representation consists of a vertex, a ray, and a line. The only edge is spanned by the vertex and the line generator, so they are adjacent:

sage: half_plane.Vrepresentation()
(A line in the direction (0, 1), A ray in the direction (1, 0), A vertex at (0, 0))
sage: half_plane.vertex_adjacency_matrix()
[0 0 1]
[0 0 0]
[1 0 0]

In one dimension higher, that is for a half-space in 3 dimensions, there is no one-dimensional face. Hence nothing is adjacent:

sage: Polyhedron(ieqs=[(0,1,0,0)]).vertex_adjacency_matrix()
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]

EXAMPLES:

In a bounded polygon, every vertex has precisely two adjacent ones:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)])
sage: for v in P.Vrep_generator():
....:     print("{} {}".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 V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
....:                rays=[(0,1)])
sage: for v in P.Vrep_generator():
....:       print("{} {}".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)

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)

The vertex adjacency matrix has base ring integers. This way one can express various counting questions:

sage: P = polytopes.cube()
sage: Q = P.stack(P.faces(2)[0])
sage: M = Q.vertex_adjacency_matrix()
sage: sum(M)
(4, 4, 3, 3, 4, 4, 4, 3, 3)
sage: G = Q.vertex_graph()
sage: G.degree()
[4, 4, 3, 3, 4, 4, 4, 3, 3]

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 one-dimensional codomain, (see sage.modules.vector_space_morphism.linear_transformation() and sage.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).
increasing – boolean (default True) 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_graph()

vertex_facet_graph(labels=True)¶

Return the vertex-facet 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 is True, then the nodes of the graph will actually be the vertices and facets of self, 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.hasse_diagram().automorphism_group())
True
sage: O = polytopes.octahedron(); O
A 3-dimensional 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: G2 = copy(G)
sage: G2.reverse_edges(G2.edges())
sage: G2.is_isomorphic(H)
True

vertex_generator()¶

Return a generator for the vertices of the polyhedron.

Warning

If the polyhedron has lines, return a generator for the vertices of the Vrepresentation. However, the represented polyhedron has no 0-dimensional faces (i.e. vertices):

sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]])
sage: list(P.vertex_generator())
[A vertex at (0, 0, 0)]
sage: P.faces(0)
()

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.

..NOTE:

The graph of a polyhedron with lines has no vertices,
as the polyhedron has no vertices (`0`-faces).

The method :meth:`Polyhedron_base:vertices` returns
the defining points in this case.

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

The graph of an unbounded polyhedron is the graph of the bounded complex:

sage: open_triangle = Polyhedron(vertices=[[1,0], [0,1]],
....:                            rays    =[[1,1]])
sage: open_triangle.vertex_graph()
Graph on 2 vertices

The graph of a polyhedron with lines has no vertices:

sage: line = Polyhedron(lines=[[0,1]])
sage: line.vertex_graph()
Graph on 0 vertices

vertices()¶

Return all vertices of the polyhedron.

OUTPUT:

A tuple of vertices.

Warning

If the polyhedron has lines, return the vertices of the Vrepresentation. However, the represented polyhedron has no 0-dimensional faces (i.e. vertices):

sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]])
sage: P.vertices()
(A vertex at (0, 0, 0),)
sage: P.faces(0)
()

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 of Vertex objects.

Warning

If the polyhedron has lines, return the vertices of the Vrepresentation. However, the represented polyhedron has no 0-dimensional faces (i.e. vertices):

sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]])
sage: P.vertices_list()
[[0, 0, 0]]
sage: P.faces(0)
()

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 or None (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. A TypeError is raised if the coordinates cannot be converted to base_ring.

Warning

If the polyhedron has lines, return the coordinates of the vertices of the Vrepresentation. However, the represented polyhedron has no 0-dimensional faces (i.e. vertices):

sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]])
sage: P.vertices_matrix()
[0]
[0]
[0]
sage: P.faces(0)
()

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, such that the unit hypercube has volume 1
- induced_lattice: Scaling of the Lebesgue measure, such that the volume of the hypercube is factorial(n)
engine – string. The backend to use. Allowed values are:
- 'auto' (default): choose engine according to measure
- 'internal': see triangulate()
- 'TOPCOM': see triangulate()
- 'lrs': use David Avis’s lrs program (optional)
- 'latte': use LattE integrale program (optional)
- 'normaliz': use Normaliz 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 lower-dimensional polytopes, we can ask for the ambient (full-dimensional), 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 lower-dimensional object:

sage: P = Polyhedron([[0, 0], [1, 1]])
sage: P.volume()
0
sage: P.volume(measure='induced')
1.414213562373095?
sage: P.volume(measure='induced_rational') # optional -- latte_int
1

sage: S = polytopes.regular_polygon(6); S
A 2-dimensional polyhedron in AA^2 defined as the convex hull of 6 vertices
sage: edge = S.faces(1)[4].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: P = Polyhedron(backend='normaliz',vertices=[[1,0,0],[0,0,1],[-1,1,1],[-1,2,0]]) # optional - pynormaliz
sage: P.volume()  # optional - pynormaliz
0
sage: P.volume(measure='induced')  # optional - pynormaliz
2.598076211353316?
sage: P.volume(measure='induced',engine='normaliz')  # optional - pynormaliz
2.598076211353316
sage: P.volume(measure='induced_rational')  # optional - pynormaliz, latte_int
3/2
sage: P.volume(measure='induced_rational',engine='normaliz')  # optional - pynormaliz
3/2
sage: P.volume(measure='induced_lattice')  # optional - pynormaliz
3

The same polytope without normaliz backend:

sage: P = Polyhedron(vertices=[[1,0,0],[0,0,1],[-1,1,1],[-1,2,0]])
sage: P.volume(measure='induced_lattice',engine='latte')  # optional - latte_int
3

sage: Dexact = polytopes.dodecahedron()
sage: v = Dexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal'); v
1.53406271079097?
sage: v = Dexact.faces(2)[4].as_polyhedron().volume(measure='induced', engine='internal'); v
1.53406271079097?
sage: RDF(v)    # abs tol 1e-9
1.53406271079044

sage: Dinexact = polytopes.dodecahedron(exact=False)
sage: w = Dinexact.faces(2)[2].as_polyhedron().volume(measure='induced', engine='internal'); RDF(w) # abs tol 1e-9
1.5340627082974878

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')
9.48683298050514?
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')
13.86542462386205?
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 full-dimensional unbounded polyhedron is infinity:

sage: P = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]])
sage: P.volume()
+Infinity

The volume of a non full-dimensional unbounded polyhedron depends on the measure used:

sage: P = Polyhedron(ieqs = [[1,1,1],[-1,-1,-1],[3,1,0]]); P
A 1-dimensional 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')  # optional - pynormaliz
+Infinity
sage: P.volume(measure='induced_rational',engine='latte')  # optional - latte_int
+Infinity

The volume in \(0\)-dimensional space is taken by counting measure:

sage: P = Polyhedron(vertices=[[]]); P
A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex
sage: P.volume()
1
sage: P = Polyhedron(vertices=[]); P
The empty polyhedron in ZZ^0
sage: P.volume()
0

wedge(face, width=1)¶

Return the wedge over a face of the polytope self.

The wedge over a face \(F\) of a polytope \(P\) with width \(w \not= 0\) is defined as:

\[(P \times \mathbb{R}) \cap \{a^\top x + |w x_{d+1}| \leq b\}\]

where \(\{x | a^\top x = b\}\) is a supporting hyperplane defining \(F\).

INPUT:

face – a PolyhedronFace of self, the face which we take the wedge over
width – a nonzero number (default: 1); specifies how wide the wedge will be

OUTPUT:

A (bounded) polyhedron

EXAMPLES:

sage: P_4 = polytopes.regular_polygon(4)
sage: W1 = P_4.wedge(P_4.faces(1)[0]); W1
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 6 vertices
sage: triangular_prism = polytopes.regular_polygon(3).prism()
sage: W1.is_combinatorially_isomorphic(triangular_prism)
True

sage: Q = polytopes.hypersimplex(4,2)
sage: W2 = Q.wedge(Q.faces(2)[7]); W2
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 9 vertices
sage: W2.vertices()
(A vertex at (1, 1, 0, 0, 1),
 A vertex at (1, 1, 0, 0, -1),
 A vertex at (1, 0, 1, 0, 1),
 A vertex at (1, 0, 1, 0, -1),
 A vertex at (1, 0, 0, 1, 1),
 A vertex at (1, 0, 0, 1, -1),
 A vertex at (0, 0, 1, 1, 0),
 A vertex at (0, 1, 1, 0, 0),
 A vertex at (0, 1, 0, 1, 0))

sage: W3 = Q.wedge(Q.faces(1)[11]); W3
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 10 vertices
sage: W3.vertices()
(A vertex at (1, 1, 0, 0, -2),
 A vertex at (1, 1, 0, 0, 2),
 A vertex at (1, 0, 1, 0, -2),
 A vertex at (1, 0, 1, 0, 2),
 A vertex at (1, 0, 0, 1, 1),
 A vertex at (1, 0, 0, 1, -1),
 A vertex at (0, 1, 0, 1, 0),
 A vertex at (0, 1, 1, 0, 1),
 A vertex at (0, 0, 1, 1, 0),
 A vertex at (0, 1, 1, 0, -1))

sage: C_3_7 = polytopes.cyclic_polytope(3,7)
sage: P_6 = polytopes.regular_polygon(6)
sage: W4 = P_6.wedge(P_6.faces(1)[0])
sage: W4.is_combinatorially_isomorphic(C_3_7.polar())
True

REFERENCES:

For more information, see Chapter 15 of [HoDaCG17].

write_cdd_Hrepresentation(filename)¶

Export the polyhedron as a H-representation to a file.

INPUT:

filename – the output file.

See also

cdd_Hrepresentation() – return the H-representation 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 V-representation to a file.

INPUT:

filename – the output file.

See also

cdd_Vrepresentation() – return the V-representation 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

Base class for polyhedra¶

Previous topic

Next topic

This Page