Base class for polyhedra: Methods for constructing new polyhedra

Except for affine hull and affine hull projection.

class sage.geometry.polyhedron.base5.Polyhedron_base5(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)[source]

Bases: Polyhedron_base4

Methods constructing new polyhedra except for affine hull and affine hull projection.

See sage.geometry.polyhedron.base.Polyhedron_base.

bipyramid()[source]

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()]; 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]]

>>> from sage.all import *
>>> octahedron = polytopes.cross_polytope(Integer(3))
>>> cross_poly_4d = octahedron.bipyramid()
>>> cross_poly_4d.n_vertices()
8
>>> q = [list(v) for v in cross_poly_4d.vertex_generator()]; 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]]

octahedron = polytopes.cross_polytope(3)
cross_poly_4d = octahedron.bipyramid()
cross_poly_4d.n_vertices()
q = [list(v) for v in cross_poly_4d.vertex_generator()]; q

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]

>>> from sage.all import *
>>> q2 = [list(v) for v in polytopes.cross_polytope(Integer(4)).vertex_generator()]
>>> [v in q2 for v in q]
[True, True, True, True, True, True, True, True]

q2 = [list(v) for v in polytopes.cross_polytope(4).vertex_generator()]
[v in q2 for v in q]
cartesian_product(other)[source]

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

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

P1 = Polyhedron([[0], [1]], base_ring=ZZ)
P2 = Polyhedron([[0], [1]], base_ring=QQ)
P1.product(P2)

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

>>> from sage.all import *
>>> P1 * P1
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> P1 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> P2 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> Integer(2) * P1
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices
>>> P1 * RealNumber('2.0')
A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices

P1 * P1
P1 * P2
P2 * P2
2 * P1
P1 * 2.0

An alias is cartesian_product():

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

>>> from sage.all import *
>>> P1.cartesian_product(P2) == P1.product(P2)
True

P1.cartesian_product(P2) == P1.product(P2)
convex_hull(other)[source]

Return the convex hull of the set-theoretic union of the two polyhedra.

INPUT:

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

>>> from sage.all import *
>>> a_simplex = polytopes.simplex(Integer(3), project=True)
>>> verts = a_simplex.vertices()
>>> verts = [[x[Integer(0)]*Integer(3)/Integer(5) + x[Integer(1)]*Integer(4)/Integer(5), -x[Integer(0)]*Integer(4)/Integer(5) + x[Integer(1)]*Integer(3)/Integer(5), x[Integer(2)]] for x in verts]
>>> another_simplex = Polyhedron(vertices=verts)
>>> simplex_union = a_simplex.convex_hull(another_simplex)
>>> simplex_union.n_vertices()
7

a_simplex = polytopes.simplex(3, project=True)
verts = a_simplex.vertices()
verts = [[x[0]*3/5 + x[1]*4/5, -x[0]*4/5 + x[1]*3/5, x[2]] for x in verts]
another_simplex = Polyhedron(vertices=verts)
simplex_union = a_simplex.convex_hull(another_simplex)
simplex_union.n_vertices()
dilation(scalar)[source]

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

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

p = Polyhedron(vertices=[[t,t^2,t^3] for t in srange(2,6)])
next(p.vertex_generator())
p2 = p.dilation(2)
next(p2.vertex_generator())
p.dilation(2) == p * 2
direct_sum(other)[source]

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:

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

>>> from sage.all import *
>>> P1 = Polyhedron([[Integer(1)], [Integer(2)]], base_ring=ZZ)
>>> P2 = Polyhedron([[Integer(3)], [Integer(4)]], base_ring=QQ)
>>> ds = P1.direct_sum(P2);ds
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> 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))

P1 = Polyhedron([[1], [2]], base_ring=ZZ)
P2 = Polyhedron([[3], [4]], base_ring=QQ)
ds = P1.direct_sum(P2);ds
ds.vertices()

See also

join() subdirect_sum()

face_split(face)[source]

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: # needs sage.rings.number_field
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)

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> pentagon  = polytopes.regular_polygon(Integer(5))
>>> f = pentagon.faces(Integer(1))[Integer(0)]
>>> fsplit_pentagon = pentagon.face_split(f)
>>> fsplit_pentagon.f_vector()
(1, 7, 14, 9, 1)

# needs sage.rings.number_field
pentagon  = polytopes.regular_polygon(5)
f = pentagon.faces(1)[0]
fsplit_pentagon = pentagon.face_split(f)
fsplit_pentagon.f_vector()

See also

one_point_suspension()

face_truncation(face, linear_coefficients=None, cut_frac=None)[source]

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())         # needs sage.combinat sage.graphs
 True

>>> from sage.all import *
>>> Cube = polytopes.hypercube(Integer(3))
>>> vertex_trunc1 = Cube.face_truncation(Cube.faces(Integer(0))[Integer(0)])
>>> vertex_trunc1.f_vector()
(1, 10, 15, 7, 1)
>>> tuple(f.ambient_V_indices() for f in vertex_trunc1.faces(Integer(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))
>>> 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))
>>> vertex_trunc2 = Cube.face_truncation(Cube.faces(Integer(0))[Integer(0)], cut_frac=Integer(1)/Integer(2))
>>> vertex_trunc2.f_vector()
(1, 10, 15, 7, 1)
>>> tuple(f.ambient_V_indices() for f in vertex_trunc2.faces(Integer(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))
>>> 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))
>>> vertex_trunc3 = Cube.face_truncation(Cube.faces(Integer(0))[Integer(0)], cut_frac=RealNumber('0.3'))
>>> 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))
>>> edge_trunc = Cube.face_truncation(Cube.faces(Integer(1))[Integer(11)])
>>> edge_trunc.f_vector()
(1, 10, 15, 7, 1)
>>> tuple(f.ambient_V_indices() for f in edge_trunc.faces(Integer(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))
>>> face_trunc = Cube.face_truncation(Cube.faces(Integer(2))[Integer(2)])
>>> 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))
>>> face_trunc.face_lattice().is_isomorphic(Cube.face_lattice())         # needs sage.combinat sage.graphs
 True

Cube = polytopes.hypercube(3)
vertex_trunc1 = Cube.face_truncation(Cube.faces(0)[0])
vertex_trunc1.f_vector()
tuple(f.ambient_V_indices() for f in vertex_trunc1.faces(2))
vertex_trunc1.vertices()
vertex_trunc2 = Cube.face_truncation(Cube.faces(0)[0], cut_frac=1/2)
vertex_trunc2.f_vector()
tuple(f.ambient_V_indices() for f in vertex_trunc2.faces(2))
vertex_trunc2.vertices()
vertex_trunc3 = Cube.face_truncation(Cube.faces(0)[0], cut_frac=0.3)
vertex_trunc3.vertices()
edge_trunc = Cube.face_truncation(Cube.faces(1)[11])
edge_trunc.f_vector()
tuple(f.ambient_V_indices() for f in edge_trunc.faces(2))
face_trunc = Cube.face_truncation(Cube.faces(2)[2])
face_trunc.vertices()
face_trunc.face_lattice().is_isomorphic(Cube.face_lattice())         # needs sage.combinat sage.graphs
intersection(other)[source]

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

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

cube = polytopes.hypercube(3)
oct = polytopes.cross_polytope(3)
cube.intersection(oct*2)

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

>>> from sage.all import *
>>> cube & oct*Integer(2)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices

cube & oct*2

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),)

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

P = Polyhedron([(0,0),(1,1)], base_ring=ZZ)
P.intersection(P)
Q = Polyhedron([(0,1),(1,0)], base_ring=ZZ)
P.intersection(Q)
_.Vrepresentation()
join(other)[source]

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

>>> from sage.all import *
>>> P1 = Polyhedron([[Integer(0)],[Integer(1)]], base_ring=ZZ)
>>> P2 = Polyhedron([[Integer(0)],[Integer(1)]], base_ring=QQ)
>>> P1.join(P2)
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
>>> P1.join(P1)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
>>> P2.join(P2)
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices

P1 = Polyhedron([[0],[1]], base_ring=ZZ)
P2 = Polyhedron([[0],[1]], base_ring=QQ)
P1.join(P2)
P1.join(P1)
P2.join(P2)

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

>>> from sage.all import *
>>> R1 = Polyhedron(rays=[[Integer(1)]])
>>> R1.join(R1)
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 2 vertices and 2 rays

R1 = Polyhedron(rays=[[1]])
R1.join(R1)
lawrence_extension(v)[source]

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

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

P = polytopes.cube()
P.lawrence_extension(P.vertices()[0])
P.lawrence_extension([-1,-1,-1])

REFERENCES:

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

lawrence_polytope()[source]

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: for i, v in enumerate(V):
....:     v = v + i*[0]
....:     P = P.lawrence_extension(v)
sage: P == L
True

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

P = polytopes.octahedron()
L = P.lawrence_polytope(); L
V = P.vertices_list()
for i, v in enumerate(V):
    v = v + i*[0]
    P = P.lawrence_extension(v)
P == L

REFERENCES:

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

linear_transformation(linear_transf, new_base_ring=None)[source]

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: # needs sage.rings.number_field
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

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

>>> # needs sage.rings.number_field
>>> square = polytopes.regular_polygon(Integer(4))
>>> square.vertices_list()
[[0, -1], [1, 0], [-1, 0], [0, 1]]
>>> transf = matrix([[Integer(1),Integer(1)], [Integer(0),Integer(1)]])
>>> sheared = transf * square
>>> sheared.vertices_list()
[[-1, -1], [1, 0], [-1, 0], [1, 1]]
>>> sheared == square.linear_transformation(transf)
True

b3 = polytopes.Birkhoff_polytope(3)
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]])
b3_proj = proj_mat * b3; b3_proj
# needs sage.rings.number_field
square = polytopes.regular_polygon(4)
square.vertices_list()
transf = matrix([[1,1], [0,1]])
sheared = transf * square
sheared.vertices_list()
sheared == square.linear_transformation(transf)

Specifying the new base ring may avoid coercion failure:

sage: # needs sage.rings.number_field
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

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> K = QuadraticField(Integer(2), names=('sqrt2',)); (sqrt2,) = K._first_ngens(1)
>>> L = QuadraticField(Integer(3), names=('sqrt3',)); (sqrt3,) = L._first_ngens(1)
>>> P = polytopes.cube()*sqrt2
>>> M = matrix([[sqrt3, Integer(0), Integer(0)], [Integer(0), sqrt3, Integer(0)], [Integer(0), Integer(0), Integer(1)]])
>>> P.linear_transformation(M, new_base_ring=K.composite_fields(L)[Integer(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

# needs sage.rings.number_field
K.<sqrt2> = QuadraticField(2)
L.<sqrt3> = QuadraticField(3)
P = polytopes.cube()*sqrt2
M = matrix([[sqrt3, 0, 0], [0, sqrt3, 0], [0, 0, 1]])
P.linear_transformation(M, new_base_ring=K.composite_fields(L)[0])

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

sage: M*P                                                                   # needs sage.rings.number_field
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?'

>>> from sage.all import *
>>> M*P                                                                   # needs sage.rings.number_field
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?'

M*P                                                                   # needs sage.rings.number_field
minkowski_difference(other)[source]

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 = \bigcap_{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.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

>>> from sage.all import *
>>> X = polytopes.hypercube(Integer(3))
>>> Y = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(1),Integer(0)), (Integer(1),Integer(0),Integer(0))]) / Integer(2)
>>> (X+Y)-Y == X
True
>>> (X-Y)+Y < X
True

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

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

>>> from sage.all import *
>>> X2 = Polyhedron(vertices=[(-Integer(1),-Integer(1),Integer(0)), (Integer(1),-Integer(1),Integer(0)), (-Integer(1),Integer(1),Integer(0)), (Integer(1),Integer(1),Integer(0))])
>>> Y2 = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(1),Integer(0),Integer(0))]) / Integer(2)
>>> (X2+Y2)-Y2 == X2
True
>>> (X2-Y2)+Y2 < X2
True

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

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

>>> from sage.all import *
>>> four_cube = polytopes.hypercube(Integer(4))
>>> four_simplex = Polyhedron(vertices=[[Integer(0), Integer(0), Integer(0), Integer(1)], [Integer(0), Integer(0), Integer(1), Integer(0)],
...                                     [Integer(0), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(0), Integer(0), Integer(0)]])
>>> four_cube - four_simplex
A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 16 vertices
>>> four_cube.minkowski_difference(four_simplex) == four_cube - four_simplex
True

four_cube = polytopes.hypercube(4)
four_simplex = Polyhedron(vertices=[[0, 0, 0, 1], [0, 0, 1, 0],
                                    [0, 1, 0, 0], [1, 0, 0, 0]])
four_cube - four_simplex
four_cube.minkowski_difference(four_simplex) == four_cube - four_simplex

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

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

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)
poly_eggs = Polyhedron([[5,4,5,4], [-4,5,-4,5],
                        [4,-5,4,-5], [0,0,0,0]], base_ring=QQ) / 100
poly_spam - poly_eggs
minkowski_sum(other)[source]

Return the Minkowski sum.

Minkowski addition of two subsets of a vector space is defined as

\[X \oplus Y = \bigcup_{y\in Y} (X+y) = \bigcup_{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.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

>>> from sage.all import *
>>> X = polytopes.hypercube(Integer(3))
>>> Y = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1)/Integer(2)), (Integer(0),Integer(1)/Integer(2),Integer(0)), (Integer(1)/Integer(2),Integer(0),Integer(0))])
>>> X+Y
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 13 vertices

>>> four_cube = polytopes.hypercube(Integer(4))
>>> four_simplex = Polyhedron(vertices=[[Integer(0), Integer(0), Integer(0), Integer(1)], [Integer(0), Integer(0), Integer(1), Integer(0)],
...                                     [Integer(0), Integer(1), Integer(0), Integer(0)], [Integer(1), Integer(0), Integer(0), Integer(0)]])
>>> four_cube + four_simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 36 vertices
>>> four_cube.minkowski_sum(four_simplex) == four_cube + four_simplex
True

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

X = polytopes.hypercube(3)
Y = Polyhedron(vertices=[(0,0,0), (0,0,1/2), (0,1/2,0), (1/2,0,0)])
X+Y
four_cube = polytopes.hypercube(4)
four_simplex = Polyhedron(vertices=[[0, 0, 0, 1], [0, 0, 1, 0],
                                    [0, 1, 0, 0], [1, 0, 0, 0]])
four_cube + four_simplex
four_cube.minkowski_sum(four_simplex) == four_cube + four_simplex
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)
poly_eggs = Polyhedron([[5,4,5,4], [-4,5,-4,5],
                        [4,-5,4,-5], [0,0,0,0]], base_ring=QQ)
poly_spam + poly_spam + poly_eggs
one_point_suspension(vertex)[source]

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: # needs sage.rings.number_field
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)

>>> from sage.all import *
>>> cube = polytopes.cube()
>>> v = cube.vertices()[Integer(0)]
>>> ops_cube = cube.one_point_suspension(v)
>>> ops_cube.f_vector()
(1, 9, 24, 24, 9, 1)

>>> # needs sage.rings.number_field
>>> pentagon  = polytopes.regular_polygon(Integer(5))
>>> v = pentagon.vertices()[Integer(0)]
>>> ops_pentagon = pentagon.one_point_suspension(v)
>>> ops_pentagon.f_vector()
(1, 6, 12, 8, 1)

cube = polytopes.cube()
v = cube.vertices()[0]
ops_cube = cube.one_point_suspension(v)
ops_cube.f_vector()
# needs sage.rings.number_field
pentagon  = polytopes.regular_polygon(5)
v = pentagon.vertices()[0]
ops_pentagon = pentagon.one_point_suspension(v)
ops_pentagon.f_vector()

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

>>> from sage.all import *
>>> vv = cube.faces(Integer(0))[Integer(1)]
>>> ops_cube2 = cube.one_point_suspension(vv)
>>> ops_cube == ops_cube2
True

vv = cube.faces(0)[1]
ops_cube2 = cube.one_point_suspension(vv)
ops_cube == ops_cube2

See also

face_split()

polar(in_affine_span=False)[source]

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); 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

>>> from sage.all import *
>>> p = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(1)], [Integer(0),Integer(1),Integer(0)], [Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(0)], [Integer(1),Integer(1),Integer(1)]],
...                base_ring=QQ); p
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices
>>> p.polar()
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices

>>> cube = polytopes.hypercube(Integer(3))
>>> octahedron = polytopes.cross_polytope(Integer(3))
>>> cube_dual = cube.polar()
>>> octahedron == cube_dual
True

p = Polyhedron(vertices=[[0,0,1], [0,1,0], [1,0,0], [0,0,0], [1,1,1]],
               base_ring=QQ); p
p.polar()
cube = polytopes.hypercube(3)
octahedron = polytopes.cross_polytope(3)
cube_dual = cube.polar()
octahedron == cube_dual

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

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

P = polytopes.simplex(3, base_ring=QQ)
P.polar(in_affine_span=True)

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

>>> from sage.all import *
>>> point = Polyhedron([[Integer(0)]])
>>> P = polytopes.cube().change_ring(QQ)
>>> (P*point).polar(in_affine_span=True) == P.polar()*point
True

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

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

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

square = polytopes.hypercube(2)
cube = square.prism()
cube
hypercube = cube.prism()
hypercube.n_vertices()
product(other)[source]

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

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

P1 = Polyhedron([[0], [1]], base_ring=ZZ)
P2 = Polyhedron([[0], [1]], base_ring=QQ)
P1.product(P2)

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

>>> from sage.all import *
>>> P1 * P1
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> P1 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> P2 * P2
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> Integer(2) * P1
A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices
>>> P1 * RealNumber('2.0')
A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices

P1 * P1
P1 * P2
P2 * P2
2 * P1
P1 * 2.0

An alias is cartesian_product():

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

>>> from sage.all import *
>>> P1.cartesian_product(P2) == P1.product(P2)
True

P1.cartesian_product(P2) == P1.product(P2)
pyramid()[source]

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)

>>> from sage.all import *
>>> square = polytopes.hypercube(Integer(2));  square
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> egyptian_pyramid = square.pyramid();  egyptian_pyramid
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices
>>> egyptian_pyramid.n_vertices()
5
>>> 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)

square = polytopes.hypercube(2);  square
egyptian_pyramid = square.pyramid();  egyptian_pyramid
egyptian_pyramid.n_vertices()
for v in egyptian_pyramid.vertex_generator(): print(v)
stack(face, position=None)[source]

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: # needs sage.rings.number_field
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)                              # needs sage.rings.number_field
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))

>>> from sage.all import *
>>> cube = polytopes.cube()
>>> square_face = cube.facets()[Integer(2)]
>>> stacked_square = cube.stack(square_face)
>>> stacked_square.f_vector()
(1, 9, 16, 9, 1)

>>> edge_face = cube.faces(Integer(1))[Integer(3)]
>>> stacked_edge = cube.stack(edge_face)
>>> stacked_edge.f_vector()
(1, 9, 17, 10, 1)

>>> cube.stack(cube.faces(Integer(0))[Integer(0)])
Traceback (most recent call last):
...
ValueError: cannot stack onto a vertex

>>> stacked_square_half = cube.stack(square_face, position=Integer(1)/Integer(2))
>>> stacked_square_half.f_vector()
(1, 9, 16, 9, 1)
>>> stacked_square_large = cube.stack(square_face, position=Integer(10))

>>> # needs sage.rings.number_field
>>> hexaprism = polytopes.regular_polygon(Integer(6)).prism()
>>> hexaprism.f_vector()
(1, 12, 18, 8, 1)
>>> square_face = hexaprism.faces(Integer(2))[Integer(2)]
>>> stacked_hexaprism = hexaprism.stack(square_face)
>>> stacked_hexaprism.f_vector()
(1, 13, 22, 11, 1)

>>> hexaprism.stack(square_face, position=Integer(4))                              # needs sage.rings.number_field
Traceback (most recent call last):
...
ValueError: the chosen position is too large

>>> s = polytopes.simplex(Integer(7))
>>> f = s.faces(Integer(3))[Integer(69)]
>>> sf = s.stack(f); sf
A 7-dimensional polyhedron in QQ^8 defined as the convex hull of 9 vertices
>>> 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))

cube = polytopes.cube()
square_face = cube.facets()[2]
stacked_square = cube.stack(square_face)
stacked_square.f_vector()
edge_face = cube.faces(1)[3]
stacked_edge = cube.stack(edge_face)
stacked_edge.f_vector()
cube.stack(cube.faces(0)[0])
stacked_square_half = cube.stack(square_face, position=1/2)
stacked_square_half.f_vector()
stacked_square_large = cube.stack(square_face, position=10)
# needs sage.rings.number_field
hexaprism = polytopes.regular_polygon(6).prism()
hexaprism.f_vector()
square_face = hexaprism.faces(2)[2]
stacked_hexaprism = hexaprism.stack(square_face)
stacked_hexaprism.f_vector()
hexaprism.stack(square_face, position=4)                              # needs sage.rings.number_field
s = polytopes.simplex(7)
f = s.faces(3)[69]
sf = s.stack(f); sf
sf.vertices()

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

>>> from sage.all import *
>>> Q = Polyhedron(vertices=[[Integer(0),Integer(1)], [Integer(1),Integer(0)]], rays=[[Integer(1),Integer(1)]])
>>> E = Q.faces(Integer(1))
>>> Q.stack(E[Integer(0)],Integer(1)/Integer(2)).Vrepresentation()
(A vertex at (0, 1),
 A vertex at (1, 0),
 A ray in the direction (1, 1),
 A vertex at (2, 0))
>>> Q.stack(E[Integer(1)],Integer(1)/Integer(2)).Vrepresentation()
(A vertex at (0, 1),
 A vertex at (0, 2),
 A vertex at (1, 0),
 A ray in the direction (1, 1))
>>> Q.stack(E[Integer(2)],Integer(1)/Integer(2)).Vrepresentation()
(A vertex at (0, 0),
 A vertex at (0, 1),
 A vertex at (1, 0),
 A ray in the direction (1, 1))

Q = Polyhedron(vertices=[[0,1], [1,0]], rays=[[1,1]])
E = Q.faces(1)
Q.stack(E[0],1/2).Vrepresentation()
Q.stack(E[1],1/2).Vrepresentation()
Q.stack(E[2],1/2).Vrepresentation()

Stacking requires a proper face:

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

>>> from sage.all import *
>>> Q.stack(Q.faces(Integer(2))[Integer(0)])
Traceback (most recent call last):
...
ValueError: can only stack on proper face

Q.stack(Q.faces(2)[0])
subdirect_sum(other)[source]

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:

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

>>> from sage.all import *
>>> P1 = Polyhedron([[Integer(1)], [Integer(2)]], base_ring=ZZ)
>>> P2 = Polyhedron([[Integer(3)], [Integer(4)]], base_ring=QQ)
>>> sds = P1.subdirect_sum(P2); sds
A 2-dimensional polyhedron in QQ^2
 defined as the convex hull of 4 vertices
>>> sds.vertices()
(A vertex at (0, 3),
 A vertex at (0, 4),
 A vertex at (1, 0),
 A vertex at (2, 0))

P1 = Polyhedron([[1], [2]], base_ring=ZZ)
P2 = Polyhedron([[3], [4]], base_ring=QQ)
sds = P1.subdirect_sum(P2); sds
sds.vertices()

See also

join() direct_sum()

translation(displacement)[source]

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

>>> from sage.all import *
>>> P = Polyhedron([[Integer(0),Integer(0)], [Integer(1),Integer(0)], [Integer(0),Integer(1)]], base_ring=ZZ)
>>> P.translation([Integer(2),Integer(1)])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices
>>> P.translation(vector(QQ, [Integer(2),Integer(1)]))
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices

P = Polyhedron([[0,0], [1,0], [0,1]], base_ring=ZZ)
P.translation([2,1])
P.translation(vector(QQ, [2,1]))
truncation(cut_frac=None)[source]

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

>>> from sage.all import *
>>> cube = polytopes.hypercube(Integer(3))
>>> trunc_cube = cube.truncation()
>>> trunc_cube.n_vertices()
24
>>> trunc_cube.n_inequalities()
14

cube = polytopes.hypercube(3)
trunc_cube = cube.truncation()
trunc_cube.n_vertices()
trunc_cube.n_inequalities()
wedge(face, width=1)[source]

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: # needs sage.rings.number_field
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)                    # needs sage.graphs
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)                                    # needs sage.rings.number_field
sage: W4 = P_6.wedge(P_6.faces(1)[0])                                       # needs sage.rings.number_field
sage: W4.is_combinatorially_isomorphic(C_3_7.polar())                       # needs sage.graphs sage.rings.number_field
True

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P_4 = polytopes.regular_polygon(Integer(4))
>>> W1 = P_4.wedge(P_4.faces(Integer(1))[Integer(0)]); W1
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 6 vertices
>>> triangular_prism = polytopes.regular_polygon(Integer(3)).prism()
>>> W1.is_combinatorially_isomorphic(triangular_prism)                    # needs sage.graphs
True

>>> Q = polytopes.hypersimplex(Integer(4),Integer(2))
>>> W2 = Q.wedge(Q.faces(Integer(2))[Integer(7)]); W2
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 9 vertices
>>> 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))

>>> W3 = Q.wedge(Q.faces(Integer(1))[Integer(11)]); W3
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 10 vertices
>>> 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))

>>> C_3_7 = polytopes.cyclic_polytope(Integer(3),Integer(7))
>>> P_6 = polytopes.regular_polygon(Integer(6))                                    # needs sage.rings.number_field
>>> W4 = P_6.wedge(P_6.faces(Integer(1))[Integer(0)])                                       # needs sage.rings.number_field
>>> W4.is_combinatorially_isomorphic(C_3_7.polar())                       # needs sage.graphs sage.rings.number_field
True

# needs sage.rings.number_field
P_4 = polytopes.regular_polygon(4)
W1 = P_4.wedge(P_4.faces(1)[0]); W1
triangular_prism = polytopes.regular_polygon(3).prism()
W1.is_combinatorially_isomorphic(triangular_prism)                    # needs sage.graphs
Q = polytopes.hypersimplex(4,2)
W2 = Q.wedge(Q.faces(2)[7]); W2
W2.vertices()
W3 = Q.wedge(Q.faces(1)[11]); W3
W3.vertices()
C_3_7 = polytopes.cyclic_polytope(3,7)
P_6 = polytopes.regular_polygon(6)                                    # needs sage.rings.number_field
W4 = P_6.wedge(P_6.faces(1)[0])                                       # needs sage.rings.number_field
W4.is_combinatorially_isomorphic(C_3_7.polar())                       # needs sage.graphs sage.rings.number_field

REFERENCES:

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