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]]
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]
- cartesian_product(other)[source]#
Return the Cartesian product.
INPUT:
other
– aPolyhedron_base
OUTPUT:
The Cartesian product of
self
andother
with a suitable base ring to encompass the two.EXAMPLES:
sage: P1 = Polyhedron([[0], [1]], base_ring=ZZ) sage: P2 = Polyhedron([[0], [1]], base_ring=QQ) sage: P1.product(P2) A 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
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
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
- convex_hull(other)[source]#
Return the convex hull of the set-theoretic union of the two polyhedra.
INPUT:
other
– aPolyhedron
OUTPUT:
The convex hull.
EXAMPLES:
sage: a_simplex = polytopes.simplex(3, project=True) sage: verts = a_simplex.vertices() sage: verts = [[x[0]*3/5 + x[1]*4/5, -x[0]*4/5 + x[1]*3/5, x[2]] for x in verts] sage: another_simplex = Polyhedron(vertices=verts) sage: simplex_union = a_simplex.convex_hull(another_simplex) sage: simplex_union.n_vertices() 7
>>> 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
- dilation(scalar)[source]#
Return the dilated (uniformly stretched) polyhedron.
INPUT:
scalar
– A scalar, not necessarily inbase_ring()
OUTPUT:
The polyhedron dilated by that scalar, possibly coerced to a bigger base ring.
EXAMPLES:
sage: p = Polyhedron(vertices=[[t,t^2,t^3] for t in srange(2,6)]) sage: next(p.vertex_generator()) A vertex at (2, 4, 8) sage: p2 = p.dilation(2) sage: next(p2.vertex_generator()) A vertex at (4, 8, 16) sage: p.dilation(2) == p * 2 True
>>> 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
- direct_sum(other)[source]#
Return the direct sum of
self
andother
.The direct sum of two polyhedron is the subdirect sum of the two, when they have the origin in their interior. To avoid checking if the origin is contained in both, we place the affine subspace containing
other
at the center ofself
.INPUT:
other
– aPolyhedron_base
EXAMPLES:
sage: P1 = Polyhedron([[1], [2]], base_ring=ZZ) sage: P2 = Polyhedron([[3], [4]], base_ring=QQ) sage: ds = P1.direct_sum(P2);ds A 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))
See also
- face_split(face)[source]#
Return the face splitting of the face
face
.Splitting a face correspond to the bipyramid (see
bipyramid()
) ofself
where the two new vertices are placed above and below the center offace
instead of the center of the whole polyhedron. The two new vertices are placed in the new dimension at height \(-1\) and \(1\).INPUT:
face
– a PolyhedronFace or a Vertex
EXAMPLES:
sage: # 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)
See also
- 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
– aPolyhedronFace
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
- intersection(other)[source]#
Return the intersection of one polyhedron with another.
INPUT:
other
– aPolyhedron
OUTPUT:
The intersection.
Note that the intersection of two \(\ZZ\)-polyhedra might not be a \(\ZZ\)-polyhedron. In this case, a \(\QQ\)-polyhedron is returned.
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: oct = polytopes.cross_polytope(3) sage: cube.intersection(oct*2) A 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
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
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),)
- join(other)[source]#
Return the join of
self
andother
.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
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
- lawrence_extension(v)[source]#
Return the Lawrence extension of
self
on the pointv
.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 ofself
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
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
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 inbase_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
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
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?'
- 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:
other
– aPolyhedron_base
OUTPUT:
The Minkowski difference of
self
andother
. Also known as Minkowski subtraction ofother
fromself
.EXAMPLES:
sage: X = polytopes.hypercube(3) sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1), (0,1,0), (1,0,0)]) / 2 sage: (X+Y)-Y == X True sage: (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
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
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
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
- 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:
other
– aPolyhedron_base
OUTPUT:
The Minkowski sum of
self
andother
EXAMPLES:
sage: X = polytopes.hypercube(3) sage: Y = Polyhedron(vertices=[(0,0,0), (0,0,1/2), (0,1/2,0), (1/2,0,0)]) sage: X+Y A 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
- one_point_suspension(vertex)[source]#
Return the one-point suspension of
self
by splitting the vertexvertex
.The resulting polyhedron has one more vertex and its dimension increases by one.
INPUT:
vertex
– a Vertex ofself
EXAMPLES:
sage: cube = polytopes.cube() sage: v = cube.vertices()[0] sage: ops_cube = cube.one_point_suspension(v) sage: ops_cube.f_vector() (1, 9, 24, 24, 9, 1) sage: # 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)
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
See also
- 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
isTrue
. Ifin_affine_span
isTrue
, 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
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
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
- 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
- product(other)[source]#
Return the Cartesian product.
INPUT:
other
– aPolyhedron_base
OUTPUT:
The Cartesian product of
self
andother
with a suitable base ring to encompass the two.EXAMPLES:
sage: P1 = Polyhedron([[0], [1]], base_ring=ZZ) sage: P2 = Polyhedron([[0], [1]], base_ring=QQ) sage: P1.product(P2) A 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
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
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
- 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)
- 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 PolyhedronFaceposition
– a positive number. Determines a relative distance from the barycenter offace
. A value close to 0 will place the new vertex close to the face and a large value further away. Default is \(1\). If the given value is too large, an error is returned.
OUTPUT:
A Polyhedron object
EXAMPLES:
sage: cube = polytopes.cube() sage: square_face = cube.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))
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))
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
- subdirect_sum(other)[source]#
Return the subdirect sum of
self
andother
.The subdirect sum of two polyhedron is a projection of the join of the two polytopes. It is obtained by placing the two objects in orthogonal subspaces intersecting at the origin.
INPUT:
other
– aPolyhedron_base
EXAMPLES:
sage: P1 = Polyhedron([[1], [2]], base_ring=ZZ) sage: P2 = Polyhedron([[3], [4]], base_ring=QQ) sage: sds = P1.subdirect_sum(P2); sds A 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))
See also
- 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
- 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
- wedge(face, width=1)[source]#
Return the wedge over a
face
of the polytopeself
.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 ofself
, the face which we take the wedge overwidth
– 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
REFERENCES:
For more information, see Chapter 15 of [HoDaCG17].