Base class for polyhedra

class sage.geometry.polyhedron.base.Polyhedron_base(parent, Vrep, Hrep, **kwds)

Bases: sage.structure.element.Element

Base class for Polyhedron objects

INPUT:

  • parent – the parent, an instance 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.

Only one of Vrep or Hrep can be different from None.

TESTS:

sage: p = Polyhedron()
sage: TestSuite(p).run()
Hrep_generator()

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

EXAMPLES:

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

Return the objects of the H-representaton. 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.n_cube(3)
sage: p.Hrepresentation(0)
An inequality (0, 0, -1) x + 1 >= 0
sage: p.Hrepresentation(0) == p.Hrepresentation() [0]
True
Hrepresentation_space()

Return the linear space containing the 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
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:

OUTPUT:

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

EXAMPLES:

sage: X = polytopes.n_cube(3)
sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1), (0,1,0), (1,0,0)]) / 2
sage: (X+Y)-Y == X
True
sage: (X-Y)+Y < X
True

The polyhedra need not be full-dimensional:

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

Minus sign is really an alias for Minkowski_difference()

sage: four_cube = polytopes.n_cube(4)
sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]])
sage: four_cube - four_simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices
sage: four_cube.Minkowski_difference(four_simplex) == four_cube - four_simplex
True

Coercion of the base ring works:

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

TESTS:

sage: X = polytopes.n_cube(2)
sage: Y = Polyhedron(vertices=[(1,1)])
sage: (X-Y).Vrepresentation()
(A vertex at (0, -2), A vertex at (0, 0), A vertex at (-2, 0), A vertex at (-2, -2))

sage: Y = Polyhedron(vertices=[(1,1), (0,0)])
sage: (X-Y).Vrepresentation()
(A vertex at (0, -1), A vertex at (0, 0), A vertex at (-1, 0), A vertex at (-1, -1))

sage: X = X + Y   # now Y is a Minkowski summand of X
sage: (X+Y)-Y == X
True
sage: (X-Y)+Y == X
True
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:

OUTPUT:

The Minkowski sum of self and other.

EXAMPLES:

sage: X = polytopes.n_cube(3)
sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1/2), (0,1/2,0), (1/2,0,0)])
sage: X+Y
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 13 vertices

sage: four_cube = polytopes.n_cube(4)
sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]])
sage: four_cube + four_simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 36 vertices
sage: four_cube.Minkowski_sum(four_simplex) == four_cube + four_simplex
True

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

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

EXAMPLES:

sage: p = polytopes.cyclic_polytope(3,4)
sage: vg = p.Vrep_generator()
sage: vg.next()
A vertex at (0, 0, 0)
sage: vg.next()
A vertex at (1, 1, 1)
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.n_simplex(4)
sage: p.Vrepresentation(0)
A vertex at (-7071/10000, 1633/4000, 7217/25000, 22361/100000)
sage: p.Vrepresentation(0) == p.Vrepresentation() [0]
True
Vrepresentation_space()

Return the ambient vector space.

OUTPUT:

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

EXAMPLES:

sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.Vrepresentation_space()
Ambient free module of rank 4 over the principal ideal domain Integer Ring
sage: poly_test.ambient_space() is poly_test.Vrepresentation_space()
True
adjacency_matrix()

Return the binary matrix of vertex adjacencies.

EXAMPLES:

sage: polytopes.n_simplex(4).vertex_adjacency_matrix()
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]

The rows and columns of the vertex adjacency matrix correspond to the Vrepresentation() objects: vertices, rays, and lines. The \((i,j)\) matrix entry equals \(1\) if the \(i\)-th and \(j\)-th V-representation object are adjacent.

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

  • 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 P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 1) A vertex at (0, 1)
(1, 0, 1, 0) A vertex at (1, 0)
(0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 1, 0) A vertex at (4, 1)

If the V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
...                  rays=[(0,1)])
sage: for v in P.Vrep_generator():
...       print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 1) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 1, 0) A vertex at (1, 0)
(0, 0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 0, 1, 0) A vertex at (4, 1)

If the V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
...                  rays=[(0,1), (1,1)])
sage: for v in P.Vrep_generator():
...       print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 0) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 0, 1) A vertex at (1, 0)
(0, 0, 0, 0, 1) A ray in the direction (1, 1)
(0, 0, 1, 1, 0) A vertex at (3, 0)
ambient_dim()

Return the dimension of the ambient space.

EXAMPLES:

sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.ambient_dim()
4
ambient_space()

Return the ambient vector space.

OUTPUT:

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

EXAMPLES:

sage: poly_test = Polyhedron(vertices = [[1,0,0,0],[0,1,0,0]])
sage: poly_test.Vrepresentation_space()
Ambient free module of rank 4 over the principal ideal domain Integer Ring
sage: poly_test.ambient_space() is poly_test.Vrepresentation_space()
True
base_extend(base_ring, backend=None)

Return a new polyhedron over a larger field.

INPUT:

  • base_ring – the new base ring.
  • backend – the new backend, see Polyhedron().

OUTPUT:

The same polyhedron, but over a larger base ring.

EXAMPLES:

sage: P = Polyhedron(vertices=[(1,0), (0,1)], rays=[(1,1)], base_ring=ZZ);  P
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.base_extend(QQ)
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
sage: P.base_extend(QQ) == P
True
base_ring()

Return the base ring.

OUTPUT:

Either QQ (exact arithmetic using gmp, default) or RDF (double precision floating-point arithmetic)

EXAMPLES:

sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]])
sage: triangle.base_ring() == ZZ
True
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]
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)

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.

OUTPUT:

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

EXAMPLES:

sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box()
((1/3, 1/3), (2/3, 2/3))
sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral=True)
((0, 0), (1, 1))
sage: polytopes.buckyball().bounding_box()
((-1059/1309, -1059/1309, -1059/1309), (1059/1309, 1059/1309, 1059/1309))
cdd_Hrepresentation()

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

OUTPUT:

A string. If you save the output to filename.ine then you can run the stand-alone cdd via cddr+ filename.ine

EXAMPLES:

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

Write the vertices/rays/lines data of the polyhedron in cdd’s V-representation format.

OUTPUT:

A string. If you save the output to filename.ext then you can run the stand-alone cdd via cddr+ filename.ext

EXAMPLES:

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

Return the average of the vertices.

See also interior_point().

OUTPUT:

The center of the polyhedron. All rays and lines are ignored. Raises a ZeroDivisionError for the empty polytope.

EXAMPLES:

sage: p = polytopes.n_cube(3)
sage: p = p + vector([1,0,0])
sage: p.center()
(1, 0, 0)
combinatorial_automorphism_group()

Computes the combinatorial automorphism group of the vertex graph of the polyhedron.

OUTPUT:

A PermutationGroup that is isomorphic to the combinatorial automorphism group is returned.

Note that in Sage, permutation groups always act on positive integers while self.Vrepresentation() is indexed by nonnegative integers. The indexing of the permutation group is chosen to be shifted by +1. That is, i in the permutation group corresponds to the V-representation object self.Vrepresentation(i-1).

EXAMPLES:

sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
sage: quadrangle.combinatorial_automorphism_group()
Permutation Group with generators [(2,3), (1,2)(3,4)]
sage: quadrangle.restricted_automorphism_group()
Permutation Group with generators [()]

Permutations can only exchange vertices with vertices, rays with rays, and lines with lines:

sage: P = Polyhedron(vertices=[(1,0,0), (1,1,0)], rays=[(1,0,0)], lines=[(0,0,1)])
sage: P.combinatorial_automorphism_group()
Permutation Group with generators [(3,4)]
contains(point)

Test whether the polyhedron contains the given point.

See also interior_contains() and relative_interior_contains().

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 #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:

OUTPUT:

The convex hull.

EXAMPLES:

sage: a_simplex = polytopes.n_simplex(3)
sage: verts = a_simplex.vertices()
sage: verts = [[x[0]*3/5+x[1]*4/5, -x[0]*4/5+x[1]*3/5, x[2]] for x in verts]
sage: another_simplex = Polyhedron(vertices = verts)
sage: simplex_union = a_simplex.convex_hull(another_simplex)
sage: simplex_union.n_vertices()
7
delete()

Delete this polyhedron.

This speeds up creation of new polyhedra by reusing objects. After recycling a polyhedron object, it is not in a consistent state any more and neither the polyhedron nor its H/V-representation objects may be used any more.

See also

recycle()

EXAMPLES:

sage: p = Polyhedron([(0,0),(1,0),(0,1)])
sage: p.delete()

sage: vertices = [(0,0,0,0),(1,0,0,0),(0,1,0,0),(1,1,0,0),(0,0,1,0),(0,0,0,1)]
sage: def loop_polyhedra():
...       for i in range(0,100):
...           p = Polyhedron(vertices)

sage: timeit('loop_polyhedra()')                   # not tested - random
5 loops, best of 3: 79.5 ms per loop

sage: def loop_polyhedra_with_recycling():
...       for i in range(0,100):
...           p = Polyhedron(vertices)
...           p.delete()

sage: timeit('loop_polyhedra_with_recycling()')    # not tested - random
5 loops, best of 3: 57.3 ms per loop
dilation(scalar)

Return the dilated (uniformly stretched) polyhedron.

INPUT:

OUTPUT:

The polyhedron dilated by that scalar, possibly coerced to a bigger field.

EXAMPLES:

sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in srange(2,6)])
sage: p.vertex_generator().next()
A vertex at (2, 4, 8)
sage: p2 = p.dilation(2)
sage: p2.vertex_generator().next()
A vertex at (4, 8, 16)
sage: p.dilation(2) == p * 2
True

TESTS:

Dilation of empty polyhedrons works, see trac ticket #14987:

sage: p = Polyhedron(ambient_dim=2); p
The empty polyhedron in ZZ^2
sage: p.dilation(3)
The empty polyhedron in ZZ^2

TESTS:

sage: p = Polyhedron(vertices=[(1,1)], rays=[(1,0)], lines=[(0,1)])
sage: (-p).rays()
(A ray in the direction (-1, 0),)
sage: (-p).lines()
(A line in the direction (0, 1),)

sage: (0*p).rays()
()
sage: (0*p).lines()
()
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 #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
edge_truncation(cut_frac=1/3)

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.n_cube(3)
sage: trunc_cube = cube.edge_truncation()
sage: trunc_cube.n_vertices()
24
sage: trunc_cube.n_inequalities()
14
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: p3.equation_generator().next()
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()

Return the f-vector.

OUTPUT:

Returns a vector whose i-th entry is the number of i-dimensional faces of the polytope.

EXAMPLES:

sage: p = Polyhedron(vertices=[[1, 2, 3], [1, 3, 2],
...       [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1], [0, 0, 0]])
sage: p.f_vector()
(1, 7, 12, 7, 1)
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:

For a full-dimensional polytope, the basic algorithm is described in Hasse_diagram_from_incidences(). There are three generalizations of [KP2002] necessary to deal with more general polytopes, corresponding to the extra H/V-representation objects:

  • Lines are removed before calling Hasse_diagram_from_incidences(), and then added back to each face V-representation except for the “empty face”.
  • Equations are removed before calling Hasse_diagram_from_incidences(), and then added back to each face H-representation.
  • Rays: Consider the half line as an example. The V-representation objects are a point and a ray, which we can think of as a point at infinity. However, the point at infinity has no inequality associated to it, so there is only one H-representation object alltogether. The face lattice does not contain the “face at infinity”. This means that in Hasse_diagram_from_incidences(), one needs to drop faces with V-representations that have no matching H-representation. In addition, one needs to ensure that every non-empty face contains at least one vertex.

EXAMPLES:

sage: square = polytopes.n_cube(2)
sage: square.face_lattice()
Finite poset containing 10 elements
sage: list(_)
[<>, <0>, <1>, <2>, <3>, <0,1>, <0,2>, <2,3>, <1,3>, <0,1,2,3>]
sage: poset_element = _[6]
sage: a_face = poset_element
sage: a_face
<0,2>
sage: a_face.dim()
1
sage: set(a_face.ambient_Vrepresentation()) ==             ...   set([square.Vrepresentation(0), square.Vrepresentation(2)])
True
sage: a_face.ambient_Vrepresentation()
(A vertex at (-1, -1), A vertex at (1, -1))
sage: a_face.ambient_Hrepresentation()
(An inequality (0, 1) x + 1 >= 0,)

A more complicated example:

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

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

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

TESTS:

sage: c5_20 = Polyhedron(vertices = [[i,i^2,i^3,i^4,i^5]
...       for i in range(1,21)])
sage: c5_20_fl = c5_20.face_lattice() # long time
sage: [len(x) for x in c5_20_fl.level_sets()] # long time
[1, 20, 190, 580, 680, 272, 1]
sage: polytopes.n_cube(2).face_lattice().plot()
sage: level_sets = polytopes.cross_polytope(2).face_lattice().level_sets()
sage: print level_sets[0], level_sets[-1]
[<>] [<0,1,2,3>]

Various degenerate polyhedra:

sage: Polyhedron(vertices=[[0,0,0],[1,0,0],[0,1,0]]).face_lattice().level_sets()
[[<>], [<0>, <1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]]
sage: Polyhedron(vertices=[(1,0,0),(0,1,0)], rays=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<1>, <2>], [<0,1>, <0,2>, <1,2>], [<0,1,2>]]
sage: Polyhedron(rays=[(1,0,0),(0,1,0)], vertices=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<0>], [<0,1>, <0,2>], [<0,1,2>]]
sage: Polyhedron(rays=[(1,0),(0,1)], vertices=[(0,0)]).face_lattice().level_sets()
[[<>], [<0>], [<0,1>, <0,2>], [<0,1,2>]]
sage: Polyhedron(vertices=[(1,),(0,)]).face_lattice().level_sets()
[[<>], [<0>, <1>], [<0,1>]]
sage: Polyhedron(vertices=[(1,0,0),(0,1,0)], lines=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<0,1>, <0,2>], [<0,1,2>]]
sage: Polyhedron(lines=[(1,0,0)], vertices=[(0,0,1)]).face_lattice().level_sets()
[[<>], [<0,1>]]
sage: Polyhedron(lines=[(1,0),(0,1)], vertices=[(0,0)]).face_lattice().level_sets()
[[<>], [<0,1,2>]]
sage: Polyhedron(lines=[(1,0)], rays=[(0,1)], vertices=[(0,0)])            ...       .face_lattice().level_sets()
[[<>], [<0,1>], [<0,1,2>]]
sage: Polyhedron(vertices=[(0,)], lines=[(1,)]).face_lattice().level_sets()
[[<>], [<0,1>]]
sage: Polyhedron(lines=[(1,0)], vertices=[(0,0)]).face_lattice().level_sets()
[[<>], [<0,1>]]

REFERENCES:

[KP2002]Volker Kaibel and Marc E. Pfetsch, “Computing the Face Lattice of a Polytope from its Vertex-Facet Incidences”, Computational Geometry: Theory and Applications, Volume 23, Issue 3 (November 2002), 281-290. Available at http://portal.acm.org/citation.cfm?id=763203 and free of charge at http://arxiv.org/abs/math/0106043
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 random but fixed.

EXAMPLES:

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

sage: p = polytopes.n_cube(4)
sage: p.faces(3)
(<0,1,2,3,4,5,6,7>, <0,1,2,3,8,9,10,11>, <0,1,4,5,8,9,12,13>,
 <0,2,4,6,8,10,12,14>, <2,3,6,7,10,11,14,15>, <8,9,10,11,12,13,14,15>,
 <4,5,6,7,12,13,14,15>, <1,3,5,7,9,11,13,15>)

sage: face = p.faces(3)[0]
sage: face.ambient_Hrepresentation()
(An inequality (1, 0, 0, 0) x + 1 >= 0,)
sage: face.vertices()
(A vertex at (-1, -1, -1, -1), A vertex at (-1, -1, -1, 1),
 A vertex at (-1, -1, 1, -1), A vertex at (-1, -1, 1, 1),
 A vertex at (-1, 1, -1, -1), A vertex at (-1, 1, -1, 1),
 A vertex at (-1, 1, 1, -1), A vertex at (-1, 1, 1, 1))

You can use the index() method to enumerate vertices and inequalities:

sage: def get_idx(rep): return rep.index()
sage: map(get_idx, face.ambient_Hrepresentation())
[4]
sage: map(get_idx, face.ambient_Vrepresentation())
[0, 1, 2, 3, 4, 5, 6, 7]

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

TESTS:

sage: pr = Polyhedron(rays = [[1,0,0],[-1,0,0],[0,1,0]], vertices = [[-1,-1,-1]], lines=[(0,0,1)])
sage: pr.faces(4)
()
sage: pr.faces(3)
(<0,1,2,3>,)
sage: pr.faces(2)
(<0,1,2>,)
sage: pr.faces(1)
()
sage: pr.faces(0)
()
sage: pr.faces(-1)
()
facet_adjacency_matrix()

Return the adjacency matrix for the facets and hyperplanes.

EXAMPLES:

sage: polytopes.n_simplex(4).facet_adjacency_matrix()
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
facial_adjacencies()

Return the list of face indices (i.e. indices of H-representation objects) and the indices of faces adjacent to them.

Note

Instead of working with face indices, it is recommended that you use the H-representation objects directly (see example).

EXAMPLES:

sage: p = polytopes.permutahedron(4)
sage: p.facial_adjacencies()[0:3]
doctest:...: DeprecationWarning:
This method is deprecated.
Use self.Hrepresentation(i).neighbors() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [1, 2, 5, 10, 12, 13]], [1, [0, 2, 5, 7, 9, 11]], [2, [0, 1, 10, 11]]]
sage: f0 = p.Hrepresentation(0)
sage: f0.index() == 0
True
sage: f0_adjacencies = [f0.index(), [n.index() for n in f0.neighbors()]]
sage: p.facial_adjacencies()[0] == f0_adjacencies
True
facial_incidences()

Return the face-vertex incidences in the form \([f_i, [v_{i_0}, v_{i_1},\dots ,v_{i_2}]]\).

Note

Instead of working with face/vertex indices, it is recommended that you use the H-representation/V-representation objects directly (see examples). Or use incidence_matrix().

OUTPUT:

The face indices are the indices of the H-representation objects, and the vertex indices are the indices of the V-representation objects.

EXAMPLES:

sage: p = Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[0,0,0],[2,2,5]])
sage: p.facial_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Hrepresentation(i).incident() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [0, 1, 3, 4]],
 [1, [0, 1, 2]],
 [2, [0, 2, 3]],
 [3, [2, 3, 4]],
 [4, [1, 2, 4]]]

sage: f0 = p.Hrepresentation(0)
sage: f0.index() == 0
True
sage: f0_incidences = [f0.index(), [v.index() for v in f0.incident()]]
sage: p.facial_incidences()[0] == f0_incidences
True

sage: p.incidence_matrix().column(0)
(1, 1, 0, 1, 1)
sage: p.incidence_matrix().column(1)
(1, 1, 1, 0, 0)
sage: p.incidence_matrix().column(2)
(1, 0, 1, 1, 0)
sage: p.incidence_matrix().column(3)
(0, 0, 1, 1, 1)
sage: p.incidence_matrix().column(4)
(0, 1, 1, 0, 1)
field()

Return the base ring.

OUTPUT:

Either QQ (exact arithmetic using gmp, default) or RDF (double precision floating-point arithmetic)

EXAMPLES:

sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]])
sage: triangle.base_ring() == ZZ
True
gale_transform()

Return the Gale transform of a polytope as described in the reference below.

OUTPUT:

A list of vectors, the Gale transform. The dimension is the dimension of the affine dependencies of the vertices of the polytope.

EXAMPLES:

This is from the reference, for a triangular prism:

sage: p = Polyhedron(vertices = [[0,0],[0,1],[1,0]])
sage: p2 = p.prism()
sage: p2.gale_transform()
[(1, 0), (0, 1), (-1, -1), (-1, 0), (0, -1), (1, 1)]

REFERENCES:

Lectures in Geometric Combinatorics, R.R.Thomas, 2006, AMS Press.
graph()

Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.

EXAMPLES:

sage: g3 = polytopes.n_cube(3).vertex_graph()
sage: len(g3.automorphism_group())
48
sage: s4 = polytopes.n_simplex(4).vertex_graph()
sage: s4.is_eulerian()
True
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.n_cube(2)
sage: p.hyperplane_arrangement()
Arrangement <-t0 + 1 | -t1 + 1 | t1 + 1 | t0 + 1>
ieqs()

Deprecated. Alias for inequalities()

EXAMPLES:

sage: p3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: p3.ieqs() == p3.inequalities()
doctest:...: DeprecationWarning:
This method is deprecated. Use inequalities() instead.
See http://trac.sagemath.org/11763 for details.
True
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()

EXAMPLES:

sage: p = polytopes.cuboctahedron()
sage: p.incidence_matrix()
[0 0 1 1 0 1 0 0 0 0 1 0 0 0]
[0 0 0 1 0 0 1 0 1 0 1 0 0 0]
[0 0 1 1 1 0 0 1 0 0 0 0 0 0]
[1 0 0 1 1 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 1 1 1 0 0 0]
[0 0 1 0 0 1 0 1 0 0 0 1 0 0]
[1 0 0 0 0 0 1 0 1 0 0 0 1 0]
[1 0 0 0 1 0 0 1 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 1 0 1 0 0]
[0 1 0 0 0 0 0 0 1 1 0 0 1 0]
[0 1 0 0 0 0 0 1 0 0 0 1 0 1]
[1 1 0 0 0 0 0 0 0 0 0 0 1 1]
sage: v = p.Vrepresentation(0)
sage: v
A vertex at (-1/2, -1/2, 0)
sage: h = p.Hrepresentation(2)
sage: h
An inequality (1, 1, -1) x + 1 >= 0
sage: h.eval(v)        # evaluation (1, 1, -1) * (-1/2, -1/2, 0) + 1
0
sage: h*v              # same as h.eval(v)
0
sage: p.incidence_matrix() [0,2]   # this entry is (v,h)
1
sage: h.contains(v)
True
sage: p.incidence_matrix() [2,0]   # note: not symmetric
0
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 algorith 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

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().columns()   # PALP
sage: for p in pts1: p.set_immutable()
sage: for p in pts2: p.set_immutable()
sage: set(pts1) == set(pts2)
True

sage: timeit('Polyhedron(v).integral_points()')   # random output
sage: timeit('LatticePolytope(v).points()')       # random output
interior_contains(point)

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

See also contains() and relative_interior_contains().

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 #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:

OUTPUT:

The intersection.

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

EXAMPLES:

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

As a shorthand, one may use:

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

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

sage: P = Polyhedron([(0,0),(1,1)], base_ring=ZZ)
sage: P.intersection(P)
A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices
sage: Q = Polyhedron([(0,1),(1,0)], base_ring=ZZ)
sage: P.intersection(Q)
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex
sage: _.Vrepresentation()
(A vertex at (1/2, 1/2),)
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.n_cube(2)
sage: B = Polyhedron(vertices=[(0,1), (1/2,1)])
sage: C = Polyhedron(vertices=[(1,1)])
sage: A.is_Minkowski_summand(B)
True
sage: A.is_Minkowski_summand(C)
True
sage: B.is_Minkowski_summand(C)
True
sage: B.is_Minkowski_summand(A)
False
sage: C.is_Minkowski_summand(A)
False
sage: C.is_Minkowski_summand(B)
False
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_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_simple()

Test for simplicity of a polytope.

See Wikipedia article Simple_polytope

EXAMPLES:

sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]])
sage: p.is_simple()
True
sage: p = Polyhedron([[0,0,0],[4,4,0],[4,0,0],[0,4,0],[2,2,2]])
sage: p.is_simple()
False
is_simplex()

Return whether the polyhedron is a simplex.

EXAMPLES:

sage: Polyhedron([(0,0,0), (1,0,0), (0,1,0)]).is_simplex()
True
sage: polytopes.n_simplex(3).is_simplex()
True
sage: polytopes.n_cube(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.n_cube(3)
sage: p.is_simplicial()
False
sage: q = polytopes.n_simplex(5)
sage: q.is_simplicial()
True
sage: p = Polyhedron([[0,0,0],[1,0,0],[0,1,0],[0,0,1]])
sage: p.is_simplicial()
True
sage: q = Polyhedron([[1,1,1],[-1,1,1],[1,-1,1],[-1,-1,1],[1,1,-1]])
sage: q.is_simplicial()
False

The method is not implemented for unbounded polyhedra:

sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
sage: p.is_simplicial()
Traceback (most recent call last):
...
NotImplementedError: This function is implemented for polytopes only.
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)
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
A lattice polytope: 2-dimensional, 4 vertices.
sage: lp.vertices()
[-1  0  0  1]
[ 0 -1  1  0]

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
A lattice polytope: 2-dimensional, 5 vertices.
sage: lp.vertices()
[-1  0  0  1  1]
[ 0 -1  1  0  1]
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: pr.line_generator().next().vector()
(1, 0)
linearities()

Deprecated. Use equations() instead. Returns the linear constraints of the polyhedron. As with inequalities, each constraint is given as [b -a1 -a2 ... an] where for variables x1, x2,..., xn, the polyhedron satisfies the equation b = a1*x1 + a2*x2 + ... + an*xn.

EXAMPLES:

sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
sage: test_p.linearities()
doctest:...: DeprecationWarning:
This method is deprecated. Use equations_list() instead.
See http://trac.sagemath.org/11763 for details.
[[-10, 1, 1, 1, 1]]
sage: test_p.linearities() == test_p.equations_list()
True
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
lrs_volume(verbose=False)

Computes the volume of a polytope using lrs.

OUTPUT:

The volume, cast to RDF (although lrs seems to output a rational value this must be an approximation in some cases).

EXAMPLES:

sage: polytopes.n_cube(3).lrs_volume() #optional - lrs
doctest:...: DeprecationWarning: use volume(engine='lrs') instead
See http://trac.sagemath.org/13249 for details.
8.0
sage: (polytopes.n_cube(3)*2).lrs_volume() #optional - lrs
64.0
sage: polytopes.twenty_four_cell().lrs_volume() #optional - lrs
2.0

REFERENCES:

David Avis’s lrs program.
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.n_simplex(4)
sage: p.n_Vrepresentation()
5
sage: p.n_Vrepresentation() == p.n_vertices() + p.n_rays() + p.n_lines()
True
n_equations()

Return the number of equations. The representation will always be minimal, so the number of equations is the codimension of the polyhedron in the ambient space.

EXAMPLES:

sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
sage: p.n_equations()
1
n_facets()

Return the number of inequalities. The representation will always be minimal, so the number of inequalities is the number of facets of the polyhedron in the ambient space.

EXAMPLES:

sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
sage: p.n_inequalities()
3

sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in range(6)])
sage: p.n_facets()
8
n_inequalities()

Return the number of inequalities. The representation will always be minimal, so the number of inequalities is the number of facets of the polyhedron in the ambient space.

EXAMPLES:

sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
sage: p.n_inequalities()
3

sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in range(6)])
sage: p.n_facets()
8
n_lines()

Return the number of lines. The representation will always be minimal.

EXAMPLES:

sage: p = Polyhedron(vertices = [[0,0]], rays=[[0,1],[0,-1]])
sage: p.n_lines()
1
n_rays()

Return the number of rays. The representation will always be minimal.

EXAMPLES:

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

Return the number of vertices. The representation will always be minimal.

EXAMPLES:

sage: p = Polyhedron(vertices = [[1,0],[0,1],[1,1]], rays=[[1,1]])
sage: p.n_vertices()
2
plot(point=None, line=None, polygon=None, wireframe='blue', fill='green', **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)
  • **kwds – optional keyword parameters that are passed to all graphics objects.

OUTPUT:

A (multipart) graphics object.

EXAMPLES:

sage: square = polytopes.n_cube(2)
sage: point = Polyhedron([[1,1]])
sage: line = Polyhedron([[1,1],[2,1]])
sage: cube = polytopes.n_cube(3)
sage: hypercube = polytopes.n_cube(4)

By default, the wireframe is rendered in blue and the fill in green:

sage: square.plot()
sage: point.plot()
sage: line.plot()
sage: cube.plot()
sage: hypercube.plot()

Draw the lines in red and nothing else:

sage: square.plot(point=False, line='red', polygon=False)
sage: point.plot(point=False, line='red', polygon=False)
sage: line.plot(point=False, line='red', polygon=False)
sage: cube.plot(point=False, line='red', polygon=False)
sage: hypercube.plot(point=False, line='red', polygon=False)

Draw points in red, no lines, and a blue polygon:

sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))

If we instead use the fill and wireframe options, the coloring depends on the dimension of the object:

sage: square.plot(fill='green', wireframe='red')
sage: point.plot(fill='green', wireframe='red')
sage: line.plot(fill='green', wireframe='red')
sage: cube.plot(fill='green', wireframe='red')
sage: hypercube.plot(fill='green', wireframe='red')

TESTS:

sage: for p in square.plot():
...       print p.options()['rgbcolor'], p
blue Point set defined by 4 point(s)
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
green Polygon defined by 4 points

sage: for p in line.plot():
...       print p.options()['rgbcolor'], p
blue Point set defined by 2 point(s)
green Line defined by 2 points

sage: for p in point.plot():
...       print p.options()['rgbcolor'], p
green Point set defined by 1 point(s)

Draw the lines in red and nothing else:

sage: for p in square.plot(point=False, line='red', polygon=False):
...       print p.options()['rgbcolor'], p
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points

Draw vertices in red, no lines, and a blue polygon:

sage: for p in square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
...       print p.options()['rgbcolor'], p
red Point set defined by 4 point(s)
(0, 0, 1) Polygon defined by 4 points

sage: for p in line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
...       print p.options()['rgbcolor'], p
red Point set defined by 2 point(s)

sage: for p in point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
...       print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)

Draw in red without wireframe:

sage: for p in square.plot(wireframe=False, fill="red"):
...       print p.options()['rgbcolor'], p
red Polygon defined by 4 points

sage: for p in line.plot(wireframe=False, fill="red"):
...       print p.options()['rgbcolor'], p
red Line defined by 2 points

sage: for p in point.plot(wireframe=False, fill="red"):
...       print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)
polar()

Return the polar (dual) polytope.

The original vertices are translated so that their barycenter is at the origin, and then the vertices are used as the coefficients in the polar inequalities.

EXAMPLES:

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

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

Return a prism of the original polyhedron.

EXAMPLES:

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

Return the cartesian product.

INPUT:

OUTPUT:

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

EXAMPLES:

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

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

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

Return a projection object.

EXAMPLES:

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

Returns a polyhedron that is a pyramid over the original.

EXAMPLES:

sage: square = polytopes.n_cube(2);  square
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: egyptian_pyramid = square.pyramid();  egyptian_pyramid
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 5 vertices
sage: egyptian_pyramid.n_vertices()
5
sage: for v in egyptian_pyramid.vertex_generator(): print v
A vertex at (0, -1, -1)
A vertex at (0, -1, 1)
A vertex at (0, 1, -1)
A vertex at (0, 1, 1)
A vertex at (1, 0, 0)
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.n_cube(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 field().

EXAMPLES:

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

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

See also contains() and 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 #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.n_cube(3)
sage: p_solid = p.render_solid(opacity = .7)
sage: type(p_solid)
<class 'sage.plot.plot3d.base.Graphics3dGroup'>
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()

Return the restricted automorphism group.

First, let the linear automorphism group be the subgroup of the Euclidean group \(E(d) = GL(d,\RR) \ltimes \RR^d\) preserving the \(d\)-dimensional polyhedron. The Euclidean group acts in the usual way \(\vec{x}\mapsto A\vec{x}+b\) on the ambient space.

The restricted automorphism group is the subgroup of the linear automorphism group generated by permutations of the generators of the same type. That is, vertices can only be permuted with vertices, ray generators with ray generators, and line generators with line generators.

For example, take the first quadrant

\[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 subgroup of rotations of the whole Euclidean group. 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}\]

OUTPUT:

A PermutationGroup that is isomorphic to the restricted automorphism group is returned.

Note that in Sage, permutation groups always act on positive integers while self.Vrepresentation() is indexed by nonnegative integers. The indexing of the permutation group is chosen to be shifted by +1. That is, i in the permutation group corresponds to the V-representation object self.Vrepresentation(i-1).

REFERENCES:

[BSS]David Bremner, Mathieu Dutour Sikiric, Achill Schuermann: Polyhedral representation conversion up to symmetries. http://arxiv.org/abs/math/0702239

EXAMPLES:

sage: P = polytopes.cross_polytope(3)
sage: AutP = P.restricted_automorphism_group();  AutP
Permutation Group with generators [(3,4), (2,3)(4,5), (2,5), (1,2)(5,6), (1,6)]
sage: P24 = polytopes.twenty_four_cell()
sage: AutP24 = P24.restricted_automorphism_group()
sage: PermutationGroup([
...     '(3,6)(4,7)(10,11)(14,15)(18,21)(19,22)',
...     '(2,3)(7,8)(11,12)(13,14)(17,18)(22,23)',
...     '(2,5)(3,10)(6,11)(8,17)(9,13)(12,16)(14,19)(15,22)(20,23)',
...     '(2,10)(3,5)(6,12)(7,18)(9,14)(11,16)(13,19)(15,23)(20,22)',
...     '(2,11)(3,12)(4,21)(5,6)(9,15)(10,16)(13,22)(14,23)(19,20)',
...     '(1,2)(3,4)(6,7)(8,9)(12,13)(16,17)(18,19)(21,22)(23,24)',
...     '(1,24)(2,13)(3,14)(5,9)(6,15)(10,19)(11,22)(12,23)(16,20)'
...   ]) == AutP24
True

Here is the quadrant example mentioned in the beginning:

sage: P = Polyhedron(rays=[(1,0),(0,1)])
sage: P.Vrepresentation()
(A vertex at (0, 0), A ray in the direction (0, 1), A ray in the direction (1, 0))
sage: P.restricted_automorphism_group()
Permutation Group with generators [(2,3)]

Also, the polyhedron need not be full-dimensional:

sage: P = Polyhedron(vertices=[(1,2,3,4,5),(7,8,9,10,11)])
sage: P.restricted_automorphism_group()
Permutation Group with generators [(1,2)]

Translations do not change the restricted automorphism group. For example, any non-degenerate triangle has the dihedral group with 6 elements, \(D_6\), as its automorphism group:

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

Floating-point computations are supported with a simple fuzzy zero implementation:

sage: P = Polyhedron(vertices=[(1.0/3.0,0,0),(0,1.0/3.0,0),(0,0,1.0/3.0)], base_ring=RDF)
sage: P.restricted_automorphism_group()
Permutation Group with generators [(2,3), (1,2)]

TESTS:

sage: p = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)])
sage: p.restricted_automorphism_group()
Permutation Group with generators [(2,3)]
schlegel_projection(projection_dir=None, height=1.1)

Returns a projection object whose transformed coordinates are a Schlegel projection of the polyhedron.

EXAMPLES:

sage: p = polytopes.n_cube(3)
sage: sch_proj = p.schlegel_projection()
sage: schlegel_edge_indices = sch_proj.lines
sage: schlegel_edges = [sch_proj.coordinates_of(x) for x in schlegel_edge_indices]
sage: len([x for x in schlegel_edges if x[0][0] > 0])
4
show(point=None, line=None, polygon=None, wireframe='blue', fill='green', **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)
  • **kwds – optional keyword parameters that are passed to all graphics objects.

OUTPUT:

A (multipart) graphics object.

EXAMPLES:

sage: square = polytopes.n_cube(2)
sage: point = Polyhedron([[1,1]])
sage: line = Polyhedron([[1,1],[2,1]])
sage: cube = polytopes.n_cube(3)
sage: hypercube = polytopes.n_cube(4)

By default, the wireframe is rendered in blue and the fill in green:

sage: square.plot()
sage: point.plot()
sage: line.plot()
sage: cube.plot()
sage: hypercube.plot()

Draw the lines in red and nothing else:

sage: square.plot(point=False, line='red', polygon=False)
sage: point.plot(point=False, line='red', polygon=False)
sage: line.plot(point=False, line='red', polygon=False)
sage: cube.plot(point=False, line='red', polygon=False)
sage: hypercube.plot(point=False, line='red', polygon=False)

Draw points in red, no lines, and a blue polygon:

sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))
sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1))

If we instead use the fill and wireframe options, the coloring depends on the dimension of the object:

sage: square.plot(fill='green', wireframe='red')
sage: point.plot(fill='green', wireframe='red')
sage: line.plot(fill='green', wireframe='red')
sage: cube.plot(fill='green', wireframe='red')
sage: hypercube.plot(fill='green', wireframe='red')

TESTS:

sage: for p in square.plot():
...       print p.options()['rgbcolor'], p
blue Point set defined by 4 point(s)
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
blue Line defined by 2 points
green Polygon defined by 4 points

sage: for p in line.plot():
...       print p.options()['rgbcolor'], p
blue Point set defined by 2 point(s)
green Line defined by 2 points

sage: for p in point.plot():
...       print p.options()['rgbcolor'], p
green Point set defined by 1 point(s)

Draw the lines in red and nothing else:

sage: for p in square.plot(point=False, line='red', polygon=False):
...       print p.options()['rgbcolor'], p
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points
red Line defined by 2 points

Draw vertices in red, no lines, and a blue polygon:

sage: for p in square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
...       print p.options()['rgbcolor'], p
red Point set defined by 4 point(s)
(0, 0, 1) Polygon defined by 4 points

sage: for p in line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
...       print p.options()['rgbcolor'], p
red Point set defined by 2 point(s)

sage: for p in point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)):
...       print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)

Draw in red without wireframe:

sage: for p in square.plot(wireframe=False, fill="red"):
...       print p.options()['rgbcolor'], p
red Polygon defined by 4 points

sage: for p in line.plot(wireframe=False, fill="red"):
...       print p.options()['rgbcolor'], p
red Line defined by 2 points

sage: for p in point.plot(wireframe=False, fill="red"):
...       print p.options()['rgbcolor'], p
red Point set defined by 1 point(s)
simplicial_complex()

Return a simplicial complex from a triangulation of the polytope.

Warning: This first triangulates the polytope using triangulated_facial_incidences, and this function may fail in dimensions greater than 3, although it usually doesn’t.

OUTPUT:

A simplicial complex.

EXAMPLES:

sage: p = polytopes.cuboctahedron()
sage: sc = p.simplicial_complex()
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate().simplicial_complex() instead.
See http://trac.sagemath.org/11634 for details.
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate() instead.
See http://trac.sagemath.org/11634 for details.
sage: sc
Simplicial complex with 12 vertices and 20 facets
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)

Returns a triangulation of the polytope.

INPUT:

  • engine – either ‘auto’ (default), ‘internal’, or ‘TOPCOM’. The latter two instruct this package to always use its own triangulation algorithms or TOPCOM’s algorithms, respectively. By default (‘auto’), TOPCOM is used if it is available and internal routines otherwise.

The remaining keyword parameters are passed through to the PointConfiguration constructor:

  • connected – boolean (default: True). Whether the triangulations should be connected to the regular triangulations via bistellar flips. These are much easier to compute than all triangulations.
  • fine – boolean (default: False). Whether the triangulations must be fine, that is, make use of all points of the configuration.
  • regular – boolean 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.n_cube(3)
sage: triangulation = cube.triangulate(
...      engine='internal') # to make doctest independent of TOPCOM
sage: triangulation
(<0,1,2,7>, <0,1,4,7>, <0,2,4,7>, <1,2,3,7>, <1,4,5,7>, <2,4,6,7>)
sage: simplex_indices = triangulation[0]; simplex_indices
(0, 1, 2, 7)
sage: simplex_vertices = [ cube.Vrepresentation(i) for i in simplex_indices ]
sage: simplex_vertices
[A vertex at (-1, -1, -1), A vertex at (-1, -1, 1),
 A vertex at (-1, 1, -1), A vertex at (1, 1, 1)]
sage: Polyhedron(simplex_vertices)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
triangulated_facial_incidences()

Return a list of the form [face_index, [v_i_0, v_i_1,...,v_i_{n-1}]] where the face_index refers to the original defining inequality. For a given face, the collection of triangles formed by each list of v_i should triangulate that face.

In dimensions greater than 3, this is computed by randomly lifting each face up a dimension; this does not always work! This should eventually be fixed by using lrs or another program that computes triangulations.

EXAMPLES:

If the figure is already composed of triangles, then all is well:

sage: Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[2,2,5]]
...             ).triangulated_facial_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate() instead.
See http://trac.sagemath.org/11634 for details.
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Hrepresentation(i).incident() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [0, 1, 2]], [1, [0, 1, 3]], [2, [0, 2, 3]], [3, [1, 2, 3]]]

Otherwise some faces get split up to triangles:

sage: Polyhedron(vertices = [[2,0,0],[4,1,0],[0,5,0],[5,5,0],
...       [1,1,0],[0,0,1]]).triangulated_facial_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use triangulate() instead.
See http://trac.sagemath.org/11634 for details.
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Vrepresentation(i).neighbors() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [1, 2, 5]], [0, [2, 5, 3]], [0, [5, 3, 4]], [1, [0, 1, 2]],
 [2, [0, 2, 3]], [3, [0, 3, 4]], [4, [0, 4, 5]], [5, [0, 1, 5]]]
vertex_adjacencies()

Return a list of vertex indices and their adjacent vertices.

Note

Instead of working with vertex indices, you can use the V-representation objects directly (see examples).

Two V-representation objects are adjacent if they generate a (1-dimensional) face of the polyhedron. Examples are two vertices of a polytope that bound an edge, or a vertex and a ray of a polyhedron that generate a bounding half-line of the polyhedron. See vertex_adjacency_matrix() for a more detailed discussion.

OUTPUT:

The vertex indices are the indices of the V-representation objects.

EXAMPLES:

sage: permuta3 = Polyhedron(vertices = Permutations([1,2,3,4]))
sage: permuta3.vertex_adjacencies()[0:3]
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Vrepresentation(i).neighbors() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [1, 2, 6]], [1, [0, 3, 7]], [2, [0, 4, 8]]]
sage: v0 = permuta3.Vrepresentation(0)
sage: v0.index() == 0
True
sage: list( v0.neighbors() )
[A vertex at (1, 2, 4, 3), A vertex at (1, 3, 2, 4), A vertex at (2, 1, 3, 4)]
sage: v0_adjacencies = [v0.index(), [v.index() for v in v0.neighbors()]]
sage: permuta3.vertex_adjacencies()[0] == v0_adjacencies
True
vertex_adjacency_matrix()

Return the binary matrix of vertex adjacencies.

EXAMPLES:

sage: polytopes.n_simplex(4).vertex_adjacency_matrix()
[0 1 1 1 1]
[1 0 1 1 1]
[1 1 0 1 1]
[1 1 1 0 1]
[1 1 1 1 0]

The rows and columns of the vertex adjacency matrix correspond to the Vrepresentation() objects: vertices, rays, and lines. The \((i,j)\) matrix entry equals \(1\) if the \(i\)-th and \(j\)-th V-representation object are adjacent.

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

  • 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 P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 1) A vertex at (0, 1)
(1, 0, 1, 0) A vertex at (1, 0)
(0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 1, 0) A vertex at (4, 1)

If the V-representation of the polygon contains vertices and one ray, then each V-representation object is adjacent to two V-representation objects:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
...                  rays=[(0,1)])
sage: for v in P.Vrep_generator():
...       print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 1) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 1, 0) A vertex at (1, 0)
(0, 0, 1, 0, 1) A vertex at (3, 0)
(1, 0, 0, 1, 0) A vertex at (4, 1)

If the V-representation of the polygon contains vertices and two distinct rays, then each vertex is adjacent to two V-representation objects (which can now be vertices or rays). The two rays are not adjacent to each other:

sage: P = Polyhedron(vertices=[(0, 1), (1, 0), (3, 0), (4, 1)],
...                  rays=[(0,1), (1,1)])
sage: for v in P.Vrep_generator():
...       print P.adjacency_matrix().row(v.index()), v
(0, 1, 0, 0, 0) A ray in the direction (0, 1)
(1, 0, 1, 0, 0) A vertex at (0, 1)
(0, 1, 0, 0, 1) A vertex at (1, 0)
(0, 0, 0, 0, 1) A ray in the direction (1, 1)
(0, 0, 1, 1, 0) A vertex at (3, 0)
vertex_generator()

Return a generator for the vertices of the polyhedron.

EXAMPLES:

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

Return a graph in which the vertices correspond to vertices of the polyhedron, and edges to edges.

EXAMPLES:

sage: g3 = polytopes.n_cube(3).vertex_graph()
sage: len(g3.automorphism_group())
48
sage: s4 = polytopes.n_simplex(4).vertex_graph()
sage: s4.is_eulerian()
True
vertex_incidences()

Return the vertex-face incidences in the form \([v_i, [f_{i_0}, f_{i_1},\dots ,f_{i_2}]]\).

Note

Instead of working with face/vertex indices, you can use the H-representation/V-representation objects directly (see examples).

EXAMPLES:

sage: p = polytopes.n_simplex(3)
sage: p.vertex_incidences()
doctest:...: DeprecationWarning:
This method is deprecated. Use self.Vrepresentation(i).incident() instead.
See http://trac.sagemath.org/11763 for details.
[[0, [0, 1, 2]], [1, [0, 1, 3]], [2, [0, 2, 3]], [3, [1, 2, 3]]]
sage: v0 = p.Vrepresentation(0)
sage: v0.index() == 0
True
sage: p.vertex_incidences()[0] == [ v0.index(), [h.index() for h in v0.incident()] ]
True
vertices()

Return all vertices of the polyhedron.

OUTPUT:

A tuple of vertices.

EXAMPLES:

sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: triangle.vertices()
(A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))
sage: a_simplex = Polyhedron(ieqs = [
...            [0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]
...        ], eqns = [[1,-1,-1,-1,-1]])
sage: a_simplex.vertices()
(A vertex at (1, 0, 0, 0), A vertex at (0, 1, 0, 0),
 A vertex at (0, 0, 1, 0), A vertex at (0, 0, 0, 1))
vertices_list()

Return a list of vertices of the polyhedron.

Note

It is recommended to use vertex_generator() instead to iterate over the list of Vertex objects.

EXAMPLES:

sage: triangle = Polyhedron(vertices=[[1,0],[0,1],[1,1]])
sage: triangle.vertices_list()
[[0, 1], [1, 0], [1, 1]]
sage: a_simplex = Polyhedron(ieqs = [
...            [0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]
...        ], eqns = [[1,-1,-1,-1,-1]])
sage: a_simplex.vertices_list()
[[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]
sage: a_simplex.vertices_list() == [list(v) for v in a_simplex.vertex_generator()]
True
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.

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(engine='auto', **kwds)

Return the volume of the polytope.

  • engine – string. The backend to use. Allowed values are:
  • **kwds – keyword arguments that are passed to the triangulation engine.

OUTPUT:

The volume of the polytope.

EXAMPLES:

sage: polytopes.n_cube(3).volume()
8
sage: (polytopes.n_cube(3)*2).volume()
64
sage: polytopes.twenty_four_cell().volume()
2

sage: polytopes.regular_polygon(5, base_ring=RDF).volume()
2.37764129...
sage: P5 = polytopes.regular_polygon(5, base_ring=QQ)
sage: P5.volume()   # rational approximation
3387471714099766473500515673753476175274812279494567801326487870013/1424719417220622426561086640229666223984528142237277803327699435400
sage: _.n()
2.37764129...

Volume of the same polytope, using the optional package lrs:

sage: P5.volume(engine='lrs') #optional - lrs
2.37764129...
sage.geometry.polyhedron.base.is_Polyhedron(X)

Test whether X is a Polyhedron.

INPUT:

  • X – anything.

OUTPUT:

Boolean.

EXAMPLES:

sage: p = polytopes.n_cube(2)
sage: from sage.geometry.polyhedron.base import is_Polyhedron
sage: is_Polyhedron(p)
True
sage: is_Polyhedron(123456)
False

Previous topic

Functions for plotting polyhedra

Next topic

Base class for polyhedra over \(\QQ\)

This Page