Base class for polyhedra¶
- class sage.geometry.polyhedron.base.Polyhedron_base(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)¶
Bases:
sage.geometry.polyhedron.base4.Polyhedron_base4
Base class for Polyhedron objects
INPUT:
parent
– the parent, an instance ofPolyhedra
.Vrep
– a list[vertices, rays, lines]
orNone
. The V-representation of the polyhedron. IfNone
, the polyhedron is determined by the H-representation.Hrep
– a list[ieqs, eqns]
orNone
. The H-representation of the polyhedron. IfNone
, the polyhedron is determined by the V-representation.Vrep_minimal
(optional) – see belowHrep_minimal
(optional) – see belowpref_rep
– string (default:None
);one of``Vrep`` or
Hrep
to pick this in case the backend cannot initialize from complete double description
mutable
– ignored
If both
Vrep
andHrep
are provided, thenVrep_minimal
andHrep_minimal
must be set toTrue
.- affine_hull(*args, **kwds)¶
Return the affine hull of
self
as a polyhedron.EXAMPLES:
sage: half_plane_in_space = Polyhedron(ieqs=[(0,1,0,0)], eqns=[(0,0,0,1)]) sage: half_plane_in_space.affine_hull().Hrepresentation() (An equation (0, 0, 1) x + 0 == 0,) sage: polytopes.cube().affine_hull().is_universe() True
- affine_hull_manifold(name=None, latex_name=None, start_index=0, ambient_space=None, ambient_chart=None, names=None, **kwds)¶
Return the affine hull of
self
as a manifold.If
self
is full-dimensional, it is just the ambient Euclidean space. Otherwise, it is a Riemannian submanifold of the ambient Euclidean space.INPUT:
ambient_space
– aEuclideanSpace
of the ambient dimension (default: the manifold ofambient_chart
, if provided; otherwise, a new instance ofEuclideanSpace
).ambient_chart
– a chart onambient_space
.names
– names for the coordinates on the affine hull.optional arguments accepted by
affine_hull_projection()
.
The default chart is determined by the optional arguments of
affine_hull_projection()
.EXAMPLES:
sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]); triangle A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices sage: A = triangle.affine_hull_manifold(name='A'); A 2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3 sage: A.embedding().display() A → E^3 (x0, x1) ↦ (x, y, z) = (t0 + x0, t0 + x1, t0 - x0 - x1 + 1) sage: A.embedding().inverse().display() E^3 → A (x, y, z) ↦ (x0, x1) = (x, y) sage: A.adapted_chart() [Chart (E^3, (x0_E3, x1_E3, t0_E3))] sage: A.normal().display() n = 1/3*sqrt(3) e_x + 1/3*sqrt(3) e_y + 1/3*sqrt(3) e_z sage: A.induced_metric() # Need to call this before volume_form Riemannian metric gamma on the 2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3 sage: A.volume_form() 2-form eps_gamma on the 2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3
Orthogonal version:
sage: A = triangle.affine_hull_manifold(name='A', orthogonal=True); A 2-dimensional Riemannian submanifold A embedded in the Euclidean space E^3 sage: A.embedding().display() A → E^3 (x0, x1) ↦ (x, y, z) = (t0 - 1/2*x0 - 1/3*x1 + 1, t0 + 1/2*x0 - 1/3*x1, t0 + 2/3*x1) sage: A.embedding().inverse().display() E^3 → A (x, y, z) ↦ (x0, x1) = (-x + y + 1, -1/2*x - 1/2*y + z + 1/2)
Arrangement of affine hull of facets:
sage: D = polytopes.dodecahedron() sage: E3 = EuclideanSpace(3) sage: submanifolds = [ ....: F.as_polyhedron().affine_hull_manifold(name=f'F{i}', orthogonal=True, ambient_space=E3) ....: for i, F in enumerate(D.facets())] sage: sum(FM.plot({}, srange(-2, 2, 0.1), srange(-2, 2, 0.1), opacity=0.2) # not tested # optional - sage.plot ....: for FM in submanifolds) + D.plot() Graphics3d Object
Full-dimensional case:
sage: cube = polytopes.cube(); cube A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: cube.affine_hull_manifold() Euclidean space E^3
- affine_hull_projection(as_polyhedron, as_affine_map=None, orthogonal=False, orthonormal=False, extend=False, minimal=False, return_all_data=False, as_convex_set=False)¶
Return the polyhedron projected into its affine hull.
Each polyhedron is contained in some smallest affine subspace (possibly the entire ambient space) – its affine hull. We provide an affine linear map that projects the ambient space of the polyhedron to the standard Euclidean space of dimension of the polyhedron, which restricts to a bijection from the affine hull.
The projection map is not unique; some parameters control the choice of the map. Other parameters control the output of the function.
INPUT:
as_polyhedron
(oras_convex_set
) – (boolean or the defaultNone
) andas_affine_map
– (boolean, defaultFalse
) control the outputThe default
as_polyhedron=None
translates toas_polyhedron=not as_affine_map
, therefore toas_polyhedron=True
if nothing is specified.If exactly one of either
as_polyhedron
oras_affine_map
is set, then either a polyhedron or the affine transformation is returned. The affine transformation sends the embedded polytope to a fulldimensional one. It is given as a pair(A, b)
, where A is a linear transformation and \(b\) is a vector, and the affine transformation sendsv
toA(v)+b
.If both
as_polyhedron
andas_affine_map
are set, then both are returned, encapsulated in an instance ofAffineHullProjectionData
.return_all_data
– (boolean, defaultFalse
)If set, then
as_polyhedron
andas_affine_map
will set (possibly overridden) and additional (internal) data concerning the transformation is returned. Everything is encapsulated in an instance ofAffineHullProjectionData
in this case.orthogonal
– boolean (default:False
); ifTrue
, provide an orthogonal transformation.orthonormal
– boolean (default:False
); ifTrue
, provide an orthonormal transformation. If the base ring does not provide the necessary square roots, the extend parameter needs to be set toTrue
.extend
– boolean (default:False
); ifTrue
, allow base ring to be extended if necessary. This becomes relevant when requiring an orthonormal transformation.minimal
– boolean (default:False
); ifTrue
, when doing an extension, it computes the minimal base ring of the extension, otherwise the base ring isAA
.
OUTPUT:
A full-dimensional polyhedron or an affine transformation, depending on the parameters
as_polyhedron
andas_affine_map
, or an instance ofAffineHullProjectionData
containing all data (parameterreturn_all_data
).If the output is an instance of
AffineHullProjectionData
, the following fields may be set:image
– the projection of the original polyhedronprojection_map
– the affine map as a pair whose first component is a linear transformation and its second component a shift; see above.section_map
– an affine map as a pair whose first component is a linear transformation and its second component a shift. It maps the codomain ofaffine_map
to the affine hull ofself
. It is a right inverse ofprojection_map
.
Note that all of these data are compatible.
Todo
make the parameters
orthogonal
andorthonormal
work with unbounded polyhedra.
EXAMPLES:
sage: triangle = Polyhedron([(1,0,0), (0,1,0), (0,0,1)]); triangle A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 3 vertices sage: triangle.affine_hull_projection() A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: half3d = Polyhedron(vertices=[(3,2,1)], rays=[(1,0,0)]) sage: half3d.affine_hull_projection().Vrepresentation() (A ray in the direction (1), A vertex at (3))
The resulting affine hulls depend on the parameter
orthogonal
andorthonormal
:sage: L = Polyhedron([[1,0],[0,1]]); L A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices sage: A = L.affine_hull_projection(); A A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (1)) sage: A = L.affine_hull_projection(orthogonal=True); A A 1-dimensional polyhedron in QQ^1 defined as the convex hull of 2 vertices sage: A.vertices() (A vertex at (0), A vertex at (2)) sage: A = L.affine_hull_projection(orthonormal=True) # optional - sage.rings.number_field Traceback (most recent call last): ... ValueError: the base ring needs to be extended; try with "extend=True" sage: A = L.affine_hull_projection(orthonormal=True, extend=True); A # optional - sage.rings.number_field A 1-dimensional polyhedron in AA^1 defined as the convex hull of 2 vertices sage: A.vertices() # optional - sage.rings.number_field (A vertex at (1.414213562373095?), A vertex at (0.?e-18))
More generally:
sage: S = polytopes.simplex(); S A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices sage: S.vertices() (A vertex at (0, 0, 0, 1), A vertex at (0, 0, 1, 0), A vertex at (0, 1, 0, 0), A vertex at (1, 0, 0, 0)) sage: A = S.affine_hull_projection(); A A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices sage: A.vertices() (A vertex at (0, 0, 0), A vertex at (0, 0, 1), A vertex at (0, 1, 0), A vertex at (1, 0, 0)) sage: A = S.affine_hull_projection(orthogonal=True); A A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices sage: A.vertices() (A vertex at (0, 0, 0), A vertex at (2, 0, 0), A vertex at (1, 3/2, 0), A vertex at (1, 1/2, 4/3)) sage: A = S.affine_hull_projection(orthonormal=True, extend=True); A A 3-dimensional polyhedron in AA^3 defined as the convex hull of 4 vertices sage: A.vertices() (A vertex at (0.7071067811865475?, 0.4082482904638630?, 1.154700538379252?), A vertex at (0.7071067811865475?, 1.224744871391589?, 0.?e-18), A vertex at (1.414213562373095?, 0.?e-18, 0.?e-18), A vertex at (0.?e-18, 0.?e-18, 0.?e-18))
With the parameter
minimal
one can get a minimal base ring:sage: s = polytopes.simplex(3) sage: s_AA = s.affine_hull_projection(orthonormal=True, extend=True) sage: s_AA.base_ring() Algebraic Real Field sage: s_full = s.affine_hull_projection(orthonormal=True, extend=True, minimal=True) sage: s_full.base_ring() Number Field in a with defining polynomial y^4 - 4*y^2 + 1 with a = 0.5176380902050415?
More examples with the
orthonormal
parameter:sage: P = polytopes.permutahedron(3); P # optional - sage.combinat # optional - sage.rings.number_field A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices sage: set([F.as_polyhedron().affine_hull_projection(orthonormal=True, extend=True).volume() for F in P.affine_hull_projection().faces(1)]) == {1, sqrt(AA(2))} # optional - sage.combinat # optional - sage.rings.number_field True sage: set([F.as_polyhedron().affine_hull_projection(orthonormal=True, extend=True).volume() for F in P.affine_hull_projection(orthonormal=True, extend=True).faces(1)]) == {sqrt(AA(2))} # optional - sage.combinat # optional - sage.rings.number_field True sage: D = polytopes.dodecahedron() # optional - sage.rings.number_field sage: F = D.faces(2)[0].as_polyhedron() # optional - sage.rings.number_field sage: F.affine_hull_projection(orthogonal=True) # optional - sage.rings.number_field A 2-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^2 defined as the convex hull of 5 vertices sage: F.affine_hull_projection(orthonormal=True, extend=True) # optional - sage.rings.number_field A 2-dimensional polyhedron in AA^2 defined as the convex hull of 5 vertices sage: K.<sqrt2> = QuadraticField(2) # optional - sage.rings.number_field sage: P = Polyhedron([2*[K.zero()],2*[sqrt2]]); P # optional - sage.rings.number_field A 1-dimensional polyhedron in (Number Field in sqrt2 with defining polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as the convex hull of 2 vertices sage: P.vertices() # optional - sage.rings.number_field (A vertex at (0, 0), A vertex at (sqrt2, sqrt2)) sage: A = P.affine_hull_projection(orthonormal=True); A # optional - sage.rings.number_field A 1-dimensional polyhedron in (Number Field in sqrt2 with defining polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^1 defined as the convex hull of 2 vertices sage: A.vertices() # optional - sage.rings.number_field (A vertex at (0), A vertex at (2)) sage: K.<sqrt3> = QuadraticField(3) # optional - sage.rings.number_field sage: P = Polyhedron([2*[K.zero()],2*[sqrt3]]); P # optional - sage.rings.number_field A 1-dimensional polyhedron in (Number Field in sqrt3 with defining polynomial x^2 - 3 with sqrt3 = 1.732050807568878?)^2 defined as the convex hull of 2 vertices sage: P.vertices() # optional - sage.rings.number_field (A vertex at (0, 0), A vertex at (sqrt3, sqrt3)) sage: A = P.affine_hull_projection(orthonormal=True) # optional - sage.rings.number_field Traceback (most recent call last): ... ValueError: the base ring needs to be extended; try with "extend=True" sage: A = P.affine_hull_projection(orthonormal=True, extend=True); A # optional - sage.rings.number_field A 1-dimensional polyhedron in AA^1 defined as the convex hull of 2 vertices sage: A.vertices() # optional - sage.rings.number_field (A vertex at (0), A vertex at (2.449489742783178?)) sage: sqrt(6).n() # optional - sage.rings.number_field 2.44948974278318
The affine hull is combinatorially equivalent to the input:
sage: P.is_combinatorially_isomorphic(P.affine_hull_projection()) # optional - sage.rings.number_field True sage: P.is_combinatorially_isomorphic(P.affine_hull_projection(orthogonal=True)) # optional - sage.rings.number_field True sage: P.is_combinatorially_isomorphic(P.affine_hull_projection(orthonormal=True, extend=True)) # optional - sage.rings.number_field True
The
orthonormal=True
parameter preserves volumes; it provides an isometric copy of the polyhedron:sage: Pentagon = polytopes.dodecahedron().faces(2)[0].as_polyhedron() # optional - sage.rings.number_field sage: P = Pentagon.affine_hull_projection(orthonormal=True, extend=True) # optional - sage.rings.number_field sage: _, c= P.is_inscribed(certificate=True) # optional - sage.rings.number_field sage: c # optional - sage.rings.number_field (0.4721359549995794?, 0.6498393924658126?) sage: circumradius = (c-vector(P.vertices()[0])).norm() # optional - sage.rings.number_field sage: p = polytopes.regular_polygon(5) # optional - sage.rings.number_field sage: p.volume() # optional - sage.rings.number_field 2.377641290737884? sage: P.volume() # optional - sage.rings.number_field 1.53406271079097? sage: p.volume()*circumradius^2 # optional - sage.rings.number_field 1.534062710790965? sage: P.volume() == p.volume()*circumradius^2 # optional - sage.rings.number_field True
One can also use
orthogonal
parameter to calculate volumes; in this case we don’t need to switch base rings. One has to divide by the square root of the determinant of the linear part of the affine transformation times its transpose:sage: Pentagon = polytopes.dodecahedron().faces(2)[0].as_polyhedron() # optional - sage.rings.number_field sage: Pnormal = Pentagon.affine_hull_projection(orthonormal=True, extend=True) # optional - sage.rings.number_field sage: Pgonal = Pentagon.affine_hull_projection(orthogonal=True) # optional - sage.rings.number_field sage: A, b = Pentagon.affine_hull_projection(orthogonal=True, as_affine_map=True) # optional - sage.rings.number_field sage: Adet = (A.matrix().transpose()*A.matrix()).det() # optional - sage.rings.number_field sage: Pnormal.volume() # optional - sage.rings.number_field 1.53406271079097? sage: Pgonal.volume()/Adet.sqrt(extend=True) # optional - sage.rings.number_field -80*(55*sqrt(5) - 123)/sqrt(-6368*sqrt(5) + 14240) sage: Pgonal.volume()/AA(Adet).sqrt().n(digits=20) # optional - sage.rings.number_field 1.5340627107909646813 sage: AA(Pgonal.volume()^2) == (Pnormal.volume()^2)*AA(Adet) # optional - sage.rings.number_field True
Another example with
as_affine_map=True
:sage: P = polytopes.permutahedron(4) # optional - sage.combinat # optional - sage.rings.number_field sage: A, b = P.affine_hull_projection(orthonormal=True, as_affine_map=True, extend=True) # optional - sage.combinat # optional - sage.rings.number_field sage: Q = P.affine_hull_projection(orthonormal=True, extend=True) # optional - sage.combinat # optional - sage.rings.number_field sage: Q.center() # optional - sage.combinat # optional - sage.rings.number_field (0.7071067811865475?, 1.224744871391589?, 1.732050807568878?) sage: A(P.center()) + b == Q.center() # optional - sage.combinat # optional - sage.rings.number_field True
For unbounded, non full-dimensional polyhedra, the
orthogonal=True
andorthonormal=True
is not implemented:sage: P = Polyhedron(ieqs=[[0, 1, 0], [0, 0, 1], [0, 0, -1]]); P A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: P.is_compact() False sage: P.is_full_dimensional() False sage: P.affine_hull_projection(orthogonal=True) Traceback (most recent call last): ... NotImplementedError: "orthogonal=True" and "orthonormal=True" work only for compact polyhedra sage: P.affine_hull_projection(orthonormal=True) Traceback (most recent call last): ... NotImplementedError: "orthogonal=True" and "orthonormal=True" work only for compact polyhedra
Setting
as_affine_map
toTrue
withoutorthogonal
ororthonormal
set toTrue
:sage: S = polytopes.simplex() sage: S.affine_hull_projection(as_affine_map=True) (Vector space morphism represented by the matrix: [1 0 0] [0 1 0] [0 0 1] [0 0 0] Domain: Vector space of dimension 4 over Rational Field Codomain: Vector space of dimension 3 over Rational Field, (0, 0, 0))
If the polyhedron is full-dimensional, it is returned:
sage: polytopes.cube().affine_hull_projection() A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: polytopes.cube().affine_hull_projection(as_affine_map=True) (Vector space morphism represented by the matrix: [1 0 0] [0 1 0] [0 0 1] Domain: Vector space of dimension 3 over Rational Field Codomain: Vector space of dimension 3 over Rational Field, (0, 0, 0))
Return polyhedron and affine map:
sage: S = polytopes.simplex(2) sage: data = S.affine_hull_projection(orthogonal=True, ....: as_polyhedron=True, ....: as_affine_map=True); data AffineHullProjectionData(image=A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices, projection_linear_map=Vector space morphism represented by the matrix: [ -1 -1/2] [ 1 -1/2] [ 0 1] Domain: Vector space of dimension 3 over Rational Field Codomain: Vector space of dimension 2 over Rational Field, projection_translation=(1, 1/2), section_linear_map=None, section_translation=None)
Return all data:
sage: data = S.affine_hull_projection(orthogonal=True, return_all_data=True); data AffineHullProjectionData(image=A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices, projection_linear_map=Vector space morphism represented by the matrix: [ -1 -1/2] [ 1 -1/2] [ 0 1] Domain: Vector space of dimension 3 over Rational Field Codomain: Vector space of dimension 2 over Rational Field, projection_translation=(1, 1/2), section_linear_map=Vector space morphism represented by the matrix: [-1/2 1/2 0] [-1/3 -1/3 2/3] Domain: Vector space of dimension 2 over Rational Field Codomain: Vector space of dimension 3 over Rational Field, section_translation=(1, 0, 0))
The section map is a right inverse of the projection map:
sage: data.image.linear_transformation(data.section_linear_map.matrix().transpose()) + data.section_translation == S True
Same without
orthogonal=True
:sage: data = S.affine_hull_projection(return_all_data=True); data AffineHullProjectionData(image=A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices, projection_linear_map=Vector space morphism represented by the matrix: [1 0] [0 1] [0 0] Domain: Vector space of dimension 3 over Rational Field Codomain: Vector space of dimension 2 over Rational Field, projection_translation=(0, 0), section_linear_map=Vector space morphism represented by the matrix: [ 1 0 -1] [ 0 1 -1] Domain: Vector space of dimension 2 over Rational Field Codomain: Vector space of dimension 3 over Rational Field, section_translation=(0, 0, 1)) sage: data.image.linear_transformation(data.section_linear_map.matrix().transpose()) + data.section_translation == S True
sage: P0 = Polyhedron( ....: ieqs=[(0, -1, 0, 1, 1, 1), (0, 1, 1, 0, -1, -1), (0, -1, 1, 1, 0, 0), ....: (0, 1, 0, 0, 0, 0), (0, 0, 1, 1, -1, -1), (0, 0, 0, 0, 0, 1), ....: (0, 0, 0, 0, 1, 0), (0, 0, 0, 1, 0, -1), (0, 0, 1, 0, 0, 0)]) sage: P = P0.intersection(Polyhedron(eqns=[(-1, 1, 1, 1, 1, 1)])) sage: P.dim() 4 sage: P.affine_hull_projection(orthogonal=True, as_affine_map=True)[0] Vector space morphism represented by the matrix: [ 0 0 0 1/3] [ -2/3 -1/6 0 -1/12] [ 1/3 -1/6 1/2 -1/12] [ 0 1/2 0 -1/12] [ 1/3 -1/6 -1/2 -1/12] Domain: Vector space of dimension 5 over Rational Field Codomain: Vector space of dimension 4 over Rational Field
- barycentric_subdivision(subdivision_frac=None)¶
Return the barycentric subdivision of a compact polyhedron.
DEFINITION:
The barycentric subdivision of a compact polyhedron is a standard way to triangulate its faces in such a way that maximal faces correspond to flags of faces of the starting polyhedron (i.e. a maximal chain in the face lattice of the polyhedron). As a simplicial complex, this is known as the order complex of the face lattice of the polyhedron.
REFERENCE:
See Wikipedia article Barycentric_subdivision Section 6.6, Handbook of Convex Geometry, Volume A, edited by P.M. Gruber and J.M. Wills. 1993, North-Holland Publishing Co..
INPUT:
subdivision_frac
– number. Gives the proportion how far the new vertices are pulled out of the polytope. Default is \(\frac{1}{3}\) and the value should be smaller than \(\frac{1}{2}\). The subdivision is computed on the polar polyhedron.
OUTPUT:
A Polyhedron object, subdivided as described above.
EXAMPLES:
sage: P = polytopes.hypercube(3) sage: P.barycentric_subdivision() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 26 vertices sage: P = Polyhedron(vertices=[[0,0,0],[0,1,0],[1,0,0],[0,0,1]]) sage: P.barycentric_subdivision() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 14 vertices sage: P = Polyhedron(vertices=[[0,1,0],[0,0,1],[1,0,0]]) sage: P.barycentric_subdivision() A 2-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices sage: P = polytopes.regular_polygon(4, base_ring=QQ) # optional - sage.rings.number_field sage: P.barycentric_subdivision() # optional - sage.rings.number_field A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 8 vertices
- bipyramid()¶
Return a polyhedron that is a bipyramid over the original.
EXAMPLES:
sage: octahedron = polytopes.cross_polytope(3) sage: cross_poly_4d = octahedron.bipyramid() sage: cross_poly_4d.n_vertices() 8 sage: q = [list(v) for v in cross_poly_4d.vertex_generator()] sage: q [[-1, 0, 0, 0], [0, -1, 0, 0], [0, 0, -1, 0], [0, 0, 0, -1], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]
Now check that bipyramids of cross-polytopes are cross-polytopes:
sage: q2 = [list(v) for v in polytopes.cross_polytope(4).vertex_generator()] sage: [v in q2 for v in q] [True, True, True, True, True, True, True, True]
- boundary_complex()¶
Return the simplicial complex given by the boundary faces of
self
, if it is simplicial.OUTPUT:
A (spherical) simplicial complex
EXAMPLES:
The boundary complex of the octahedron:
sage: oc = polytopes.octahedron() sage: sc_oc = oc.boundary_complex() sage: fl_oc = oc.face_lattice() sage: fl_sc = sc_oc.face_poset() sage: [len(x) for x in fl_oc.level_sets()] [1, 6, 12, 8, 1] sage: [len(x) for x in fl_sc.level_sets()] [6, 12, 8] sage: sc_oc.euler_characteristic() 2 sage: sc_oc.homology() {0: 0, 1: 0, 2: Z}
The polyhedron should be simplicial:
sage: c = polytopes.cube() sage: c.boundary_complex() Traceback (most recent call last): ... NotImplementedError: this function is only implemented for simplicial polytopes
- bounding_box(integral=False, integral_hull=False)¶
Return the coordinates of a rectangular box containing the non-empty polytope.
INPUT:
integral
– Boolean (default:False
). Whether to only allow integral coordinates in the bounding box.integral_hull
– Boolean (default:False
). IfTrue
, return a box containing the integral points of the polytope, orNone, None
if it is known that the polytope has no integral points.
OUTPUT:
A pair of tuples
(box_min, box_max)
wherebox_min
are the coordinates of a point bounding the coordinates of the polytope from below andbox_max
bounds the coordinates from above.EXAMPLES:
sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box() ((1/3, 1/3), (2/3, 2/3)) sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral=True) ((0, 0), (1, 1)) sage: Polyhedron([ (1/3,2/3), (2/3, 1/3) ]).bounding_box(integral_hull=True) (None, None) sage: Polyhedron([ (1/3,2/3), (3/3, 4/3) ]).bounding_box(integral_hull=True) ((1, 1), (1, 1)) sage: polytopes.buckyball(exact=False).bounding_box() ((-0.8090169944, -0.8090169944, -0.8090169944), (0.8090169944, 0.8090169944, 0.8090169944))
- cartesian_product(other)¶
Return the Cartesian product.
INPUT:
other
– aPolyhedron_base
OUTPUT:
The Cartesian product of
self
andother
with a suitable base ring to encompass the two.EXAMPLES:
sage: P1 = Polyhedron([[0],[1]], base_ring=ZZ) sage: P2 = Polyhedron([[0],[1]], base_ring=QQ) sage: P1.product(P2) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
The Cartesian product is the product in the semiring of polyhedra:
sage: P1 * P1 A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: P1 * P2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: P2 * P2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: 2 * P1 A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices sage: P1 * 2.0 A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices
An alias is
cartesian_product()
:sage: P1.cartesian_product(P2) == P1.product(P2) True
- cdd_Hrepresentation()¶
Write the inequalities/equations data of the polyhedron in cdd’s H-representation format.
See also
write_cdd_Hrepresentation()
– export the polyhedron as a H-representation to a file.OUTPUT: a string
EXAMPLES:
sage: p = polytopes.hypercube(2) sage: print(p.cdd_Hrepresentation()) H-representation begin 4 3 rational 1 -1 0 1 0 -1 1 1 0 1 0 1 end sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]],base_ring=AA) sage: triangle.base_ring() Algebraic Real Field sage: triangle.cdd_Hrepresentation() Traceback (most recent call last): ... TypeError: the base ring must be ZZ, QQ, or RDF
- cdd_Vrepresentation()¶
Write the vertices/rays/lines data of the polyhedron in cdd’s V-representation format.
See also
write_cdd_Vrepresentation()
– export the polyhedron as a V-representation to a file.OUTPUT: a string
EXAMPLES:
sage: q = Polyhedron(vertices = [[1,1],[0,0],[1,0],[0,1]]) sage: print(q.cdd_Vrepresentation()) V-representation begin 4 3 rational 1 0 0 1 0 1 1 1 0 1 1 1 end
- center()¶
Return the average of the vertices.
See also
sage.geometry.polyhedron.base1.Polyhedron_base1.representative_point()
.OUTPUT:
The center of the polyhedron. All rays and lines are ignored. Raises a
ZeroDivisionError
for the empty polytope.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p = p + vector([1,0,0]) sage: p.center() (1, 0, 0)
- centroid(engine='auto', **kwds)¶
Return the center of the mass of the polytope.
The mass is taken with respect to the induced Lebesgue measure, see
volume()
.If the polyhedron is not compact, a
NotImplementedError
is raised.INPUT:
engine
– either ‘auto’ (default), ‘internal’, ‘TOPCOM’, or ‘normaliz’. The ‘internal’ and ‘TOPCOM’ instruct this package to always use its own triangulation algorithms or TOPCOM’s algorithms, respectively. By default (‘auto’), TOPCOM is used if it is available and internal routines otherwise.**kwds
– keyword arguments that are passed to the triangulation engine (seetriangulate()
).
OUTPUT: The centroid as vector.
ALGORITHM:
We triangulate the polytope and find the barycenter of the simplices. We add the individual barycenters weighted by the fraction of the total mass.
EXAMPLES:
sage: P = polytopes.hypercube(2).pyramid() sage: P.centroid() (1/4, 0, 0) sage: P = polytopes.associahedron(['A',2]) sage: P.centroid() (2/21, 2/21) sage: P = polytopes.permutahedron(4, backend='normaliz') # optional - pynormaliz sage: P.centroid() # optional - pynormaliz (5/2, 5/2, 5/2, 5/2)
The method is not implemented for unbounded polyhedra:
sage: P = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)]) sage: P.centroid() Traceback (most recent call last): ... NotImplementedError: the polyhedron is not compact
The centroid of an empty polyhedron is not defined:
sage: Polyhedron().centroid() Traceback (most recent call last): ... ZeroDivisionError: rational division by zero
- convex_hull(other)¶
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
- dilation(scalar)¶
Return the dilated (uniformly stretched) polyhedron.
INPUT:
scalar
– A scalar, not necessarily inbase_ring()
OUTPUT:
The polyhedron dilated by that scalar, possibly coerced to a bigger base ring.
EXAMPLES:
sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in srange(2,6)]) sage: next(p.vertex_generator()) A vertex at (2, 4, 8) sage: p2 = p.dilation(2) sage: next(p2.vertex_generator()) A vertex at (4, 8, 16) sage: p.dilation(2) == p * 2 True
- direct_sum(other)¶
Return the direct sum of
self
andother
.The direct sum of two polyhedron is the subdirect sum of the two, when they have the origin in their interior. To avoid checking if the origin is contained in both, we place the affine subspace containing
other
at the center ofself
.INPUT:
other
– aPolyhedron_base
EXAMPLES:
sage: P1 = Polyhedron([[1],[2]], base_ring=ZZ) sage: P2 = Polyhedron([[3],[4]], base_ring=QQ) sage: ds = P1.direct_sum(P2);ds A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: ds.vertices() (A vertex at (1, 0), A vertex at (2, 0), A vertex at (3/2, -1/2), A vertex at (3/2, 1/2))
See also
- face_fan()¶
Return the face fan of a compact rational polyhedron.
OUTPUT:
A fan of the ambient space as a
RationalPolyhedralFan
.See also
EXAMPLES:
sage: T = polytopes.cuboctahedron() sage: T.face_fan() Rational polyhedral fan in 3-d lattice M
The polytope should contain the origin in the interior:
sage: P = Polyhedron(vertices = [[1/2, 1], [1, 1/2]]) sage: P.face_fan() Traceback (most recent call last): ... ValueError: face fans are defined only for polytopes containing the origin as an interior point! sage: Q = Polyhedron(vertices = [[-1, 1/2], [1, -1/2]]) sage: Q.contains([0,0]) True sage: FF = Q.face_fan(); FF Rational polyhedral fan in 2-d lattice M
The polytope has to have rational coordinates:
sage: S = polytopes.dodecahedron() sage: S.face_fan() Traceback (most recent call last): ... NotImplementedError: face fan handles only polytopes over the rationals
REFERENCES:
For more information, see Chapter 7 of [Zie2007].
- face_split(face)¶
Return the face splitting of the face
face
.Splitting a face correspond to the bipyramid (see
bipyramid()
) ofself
where the two new vertices are placed above and below the center offace
instead of the center of the whole polyhedron. The two new vertices are placed in the new dimension at height \(-1\) and \(1\).INPUT:
face
– a PolyhedronFace or a Vertex
EXAMPLES:
sage: pentagon = polytopes.regular_polygon(5) # optional - sage.rings.number_field sage: f = pentagon.faces(1)[0] # optional - sage.rings.number_field sage: fsplit_pentagon = pentagon.face_split(f) # optional - sage.rings.number_field sage: fsplit_pentagon.f_vector() # optional - sage.rings.number_field (1, 7, 14, 9, 1)
See also
- face_truncation(face, linear_coefficients=None, cut_frac=None)¶
Return a new polyhedron formed by truncating a face by an hyperplane.
By default, the normal vector of the hyperplane used to truncate the polyhedron is obtained by taking the barycenter vector of the cone corresponding to the truncated face in the normal fan of the polyhedron. It is possible to change the direction using the option
linear_coefficients
.To determine how deep the truncation is done, the method uses the parameter
cut_frac
. By default it is equal to \(\frac{1}{3}\). Once the normal vector of the cutting hyperplane is chosen, the vertices of polyhedron are evaluated according to the corresponding linear function. The parameter \(\frac{1}{3}\) means that the cutting hyperplane is placed \(\frac{1}{3}\) of the way from the vertices of the truncated face to the next evaluated vertex.INPUT:
face
– a PolyhedronFacelinear_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 thehyperplane cuts the polyhedron. A value close to 0 cuts very close to the face, whereas a value close to 1 cuts very close to the next vertex (according to the normal vector of the cutting hyperplane). Default is \(\frac{1}{3}\).
OUTPUT:
A Polyhedron object, truncated as described above.
EXAMPLES:
sage: Cube = polytopes.hypercube(3) sage: vertex_trunc1 = Cube.face_truncation(Cube.faces(0)[0]) sage: vertex_trunc1.f_vector() (1, 10, 15, 7, 1) sage: tuple(f.ambient_V_indices() for f in vertex_trunc1.faces(2)) ((4, 5, 6, 7, 9), (0, 3, 4, 8, 9), (0, 1, 6, 7, 8), (7, 8, 9), (2, 3, 4, 5), (1, 2, 5, 6), (0, 1, 2, 3)) sage: vertex_trunc1.vertices() (A vertex at (1, -1, -1), A vertex at (1, 1, -1), A vertex at (1, 1, 1), A vertex at (1, -1, 1), A vertex at (-1, -1, 1), A vertex at (-1, 1, 1), A vertex at (-1, 1, -1), A vertex at (-1, -1/3, -1), A vertex at (-1/3, -1, -1), A vertex at (-1, -1, -1/3)) sage: vertex_trunc2 = Cube.face_truncation(Cube.faces(0)[0],cut_frac=1/2) sage: vertex_trunc2.f_vector() (1, 10, 15, 7, 1) sage: tuple(f.ambient_V_indices() for f in vertex_trunc2.faces(2)) ((4, 5, 6, 7, 9), (0, 3, 4, 8, 9), (0, 1, 6, 7, 8), (7, 8, 9), (2, 3, 4, 5), (1, 2, 5, 6), (0, 1, 2, 3)) sage: vertex_trunc2.vertices() (A vertex at (1, -1, -1), A vertex at (1, 1, -1), A vertex at (1, 1, 1), A vertex at (1, -1, 1), A vertex at (-1, -1, 1), A vertex at (-1, 1, 1), A vertex at (-1, 1, -1), A vertex at (-1, 0, -1), A vertex at (0, -1, -1), A vertex at (-1, -1, 0)) sage: vertex_trunc3 = Cube.face_truncation(Cube.faces(0)[0],cut_frac=0.3) sage: vertex_trunc3.vertices() (A vertex at (-1.0, -1.0, 1.0), A vertex at (-1.0, 1.0, -1.0), A vertex at (-1.0, 1.0, 1.0), A vertex at (1.0, 1.0, -1.0), A vertex at (1.0, 1.0, 1.0), A vertex at (1.0, -1.0, 1.0), A vertex at (1.0, -1.0, -1.0), A vertex at (-0.4, -1.0, -1.0), A vertex at (-1.0, -0.4, -1.0), A vertex at (-1.0, -1.0, -0.4)) sage: edge_trunc = Cube.face_truncation(Cube.faces(1)[11]) sage: edge_trunc.f_vector() (1, 10, 15, 7, 1) sage: tuple(f.ambient_V_indices() for f in edge_trunc.faces(2)) ((0, 5, 6, 7), (1, 4, 5, 6, 8), (6, 7, 8, 9), (0, 2, 3, 7, 9), (1, 2, 8, 9), (0, 3, 4, 5), (1, 2, 3, 4)) sage: face_trunc = Cube.face_truncation(Cube.faces(2)[2]) sage: face_trunc.vertices() (A vertex at (1, -1, -1), A vertex at (1, 1, -1), A vertex at (1, 1, 1), A vertex at (1, -1, 1), A vertex at (-1/3, -1, 1), A vertex at (-1/3, 1, 1), A vertex at (-1/3, 1, -1), A vertex at (-1/3, -1, -1)) sage: face_trunc.face_lattice().is_isomorphic(Cube.face_lattice()) True
- gale_transform()¶
Return the Gale transform of a polytope as described in the reference below.
OUTPUT:
A list of vectors, the Gale transform. The dimension is the dimension of the affine dependencies of the vertices of the polytope.
EXAMPLES:
This is from the reference, for a triangular prism:
sage: p = Polyhedron(vertices = [[0,0],[0,1],[1,0]]) sage: p2 = p.prism() sage: p2.gale_transform() ((-1, 0), (0, -1), (1, 1), (-1, -1), (1, 0), (0, 1))
REFERENCES:
Lectures in Geometric Combinatorics, R.R.Thomas, 2006, AMS Press.
See also
:func`~sage.geometry.polyhedron.library.gale_transform_to_polyhedron`.
- hyperplane_arrangement()¶
Return the hyperplane arrangement defined by the equations and inequalities.
OUTPUT:
A
hyperplane arrangement
consisting of the hyperplanes defined by theHrepresentation()
. If the polytope is full-dimensional, this is the hyperplane arrangement spanned by the facets of the polyhedron.EXAMPLES:
sage: p = polytopes.hypercube(2) sage: p.hyperplane_arrangement() Arrangement <-t0 + 1 | -t1 + 1 | t1 + 1 | t0 + 1>
- integrate(function, measure='ambient', **kwds)¶
Return the integral of
function
over this polytope.INPUT:
self
– Polyhedronfunction
– a multivariate polynomial or a valid LattE description string for polynomialsmeasure
– string, the measure to useAllowed values are:
ambient
(default): Lebesgue measure of ambient space,induced
: Lebesgue measure of the affine hull,induced_nonnormalized
: Lebesgue measure of the affine hull without the normalization by \(\sqrt{\det(A^\top A)}\) (with \(A\) being the affine transformation matrix; seeaffine_hull()
).
**kwds
– additional keyword arguments that are passed to the engine
OUTPUT:
The integral of the polynomial over the polytope
Note
The polytope triangulation algorithm is used. This function depends on LattE (i.e., the
latte_int
optional package).EXAMPLES:
sage: P = polytopes.cube() sage: x, y, z = polygens(QQ, 'x, y, z') sage: P.integrate(x^2*y^2*z^2) # optional - latte_int 8/27
If the polyhedron has floating point coordinates, an inexact result can be obtained if we transform to rational coordinates:
sage: P = 1.4142*polytopes.cube() sage: P_QQ = Polyhedron(vertices=[[QQ(vi) for vi in v] for v in P.vertex_generator()]) sage: RDF(P_QQ.integrate(x^2*y^2*z^2)) # optional - latte_int 6.703841212195228
Integral over a non full-dimensional polytope:
sage: x, y = polygens(QQ, 'x, y') sage: P = Polyhedron(vertices=[[0,0],[1,1]]) sage: P.integrate(x*y) # optional - latte_int 0 sage: ixy = P.integrate(x*y, measure='induced'); ixy # optional - latte_int 0.4714045207910317? sage: ixy.parent() # optional - latte_int Algebraic Real Field
Convert to a symbolic expression:
sage: ixy.radical_expression() # optional - latte_int 1/3*sqrt(2)
Another non full-dimensional polytope integration:
sage: R.<x, y, z> = QQ[] sage: P = polytopes.simplex(2) sage: V = AA(P.volume(measure='induced')); V.radical_expression() 1/2*sqrt(3) sage: P.integrate(R(1), measure='induced') == V # optional - latte_int True
Computing the mass center:
sage: (P.integrate(x, measure='induced') / V).radical_expression() # optional - latte_int 1/3 sage: (P.integrate(y, measure='induced') / V).radical_expression() # optional - latte_int 1/3 sage: (P.integrate(z, measure='induced') / V).radical_expression() # optional - latte_int 1/3
- intersection(other)¶
Return the intersection of one polyhedron with another.
INPUT:
other
– aPolyhedron
OUTPUT:
The intersection.
Note that the intersection of two \(\ZZ\)-polyhedra might not be a \(\ZZ\)-polyhedron. In this case, a \(\QQ\)-polyhedron is returned.
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: oct = polytopes.cross_polytope(3) sage: cube.intersection(oct*2) A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
As a shorthand, one may use:
sage: cube & oct*2 A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 12 vertices
The intersection of two \(\ZZ\)-polyhedra is not necessarily a \(\ZZ\)-polyhedron:
sage: P = Polyhedron([(0,0),(1,1)], base_ring=ZZ) sage: P.intersection(P) A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices sage: Q = Polyhedron([(0,1),(1,0)], base_ring=ZZ) sage: P.intersection(Q) A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex sage: _.Vrepresentation() (A vertex at (1/2, 1/2),)
- is_inscribed(certificate=False)¶
This function tests whether the vertices of the polyhedron are inscribed on a sphere.
The polyhedron is expected to be compact and full-dimensional. A full-dimensional compact polytope is inscribed if there exists a point in space which is equidistant to all its vertices.
ALGORITHM:
The function first computes the circumsphere of a full-dimensional simplex with vertices of
self
. It is found by lifting the points on a paraboloid to find the hyperplane on which the circumsphere is lifted. Then, it checks if all other vertices are equidistant to the circumcenter of that simplex.INPUT:
certificate
– (default:False
) boolean; specifies whether to return the circumcenter, if found.
OUTPUT:
If
certificate
is true, returns a tuple containing:Boolean.
The circumcenter of the polytope or None.
If
certificate
is false:a Boolean.
EXAMPLES:
sage: q = Polyhedron(vertices = [[1,1,1,1],[-1,-1,1,1],[1,-1,-1,1], ....: [-1,1,-1,1],[1,1,1,-1],[-1,-1,1,-1], ....: [1,-1,-1,-1],[-1,1,-1,-1],[0,0,10/13,-24/13], ....: [0,0,-10/13,-24/13]]) sage: q.is_inscribed(certificate=True) (True, (0, 0, 0, 0)) sage: cube = polytopes.cube() sage: cube.is_inscribed() True sage: translated_cube = Polyhedron(vertices=[v.vector() + vector([1,2,3]) ....: for v in cube.vertices()]) sage: translated_cube.is_inscribed(certificate=True) (True, (1, 2, 3)) sage: truncated_cube = cube.face_truncation(cube.faces(0)[0]) sage: truncated_cube.is_inscribed() False
The method is not implemented for non-full-dimensional polytope or unbounded polyhedra:
sage: square = Polyhedron(vertices=[[1,0,0],[0,1,0],[1,1,0],[0,0,0]]) sage: square.is_inscribed() Traceback (most recent call last): ... NotImplementedError: this function is implemented for full-dimensional polyhedra only sage: p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)]) sage: p.is_inscribed() Traceback (most recent call last): ... NotImplementedError: this function is not implemented for unbounded polyhedra
- is_minkowski_summand(Y)¶
Test whether
Y
is a Minkowski summand.See
minkowski_sum()
.OUTPUT:
Boolean. Whether there exists another polyhedron \(Z\) such that
self
can be written as \(Y\oplus Z\).EXAMPLES:
sage: A = polytopes.hypercube(2) sage: B = Polyhedron(vertices=[(0,1), (1/2,1)]) sage: C = Polyhedron(vertices=[(1,1)]) sage: A.is_minkowski_summand(B) True sage: A.is_minkowski_summand(C) True sage: B.is_minkowski_summand(C) True sage: B.is_minkowski_summand(A) False sage: C.is_minkowski_summand(A) False sage: C.is_minkowski_summand(B) False
- join(other)¶
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
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
- lawrence_extension(v)¶
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
REFERENCES:
For more information, see Section 6.6 of [Zie2007].
- lawrence_polytope()¶
Return the Lawrence polytope of
self
.Let \(P\) be a \(d\)-polytope in \(\RR^r\) with \(n\) vertices. The Lawrence polytope of \(P\) is the polytope whose vertices are the columns of the following \((r+n)\)-by-\(2n\) matrix.
\[\begin{split}\begin{pmatrix} V & V \\ I_n & 2I_n \end{pmatrix},\end{split}\]where \(V\) is the \(r\)-by-\(n\) vertices matrix of \(P\).
EXAMPLES:
sage: P = polytopes.octahedron() sage: L = P.lawrence_polytope(); L A 9-dimensional polyhedron in ZZ^9 defined as the convex hull of 12 vertices sage: V = P.vertices_list() sage: i = 0 sage: for v in V: ....: v = v + i*[0] ....: P = P.lawrence_extension(v) ....: i = i + 1 sage: P == L True
REFERENCES:
For more information, see Section 6.6 of [Zie2007].
- linear_transformation(linear_transf, new_base_ring=None)¶
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: square = polytopes.regular_polygon(4) # optional - sage.rings.number_field sage: square.vertices_list() # optional - sage.rings.number_field [[0, -1], [1, 0], [-1, 0], [0, 1]] sage: transf = matrix([[1,1],[0,1]]) # optional - sage.rings.number_field sage: sheared = transf * square # optional - sage.rings.number_field sage: sheared.vertices_list() # optional - sage.rings.number_field [[-1, -1], [1, 0], [-1, 0], [1, 1]] sage: sheared == square.linear_transformation(transf) # optional - sage.rings.number_field True
Specifying the new base ring may avoid coercion failure:
sage: K.<sqrt2> = QuadraticField(2) # optional - sage.rings.number_field sage: L.<sqrt3> = QuadraticField(3) # optional - sage.rings.number_field sage: P = polytopes.cube()*sqrt2 # optional - sage.rings.number_field sage: M = matrix([[sqrt3, 0, 0], [0, sqrt3, 0], [0, 0, 1]]) # optional - sage.rings.number_field sage: P.linear_transformation(M, new_base_ring=K.composite_fields(L)[0]) # optional - sage.rings.number_field 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 # optional - 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)¶
Return the Minkowski difference.
Minkowski subtraction can equivalently be defined via Minkowski addition (see
minkowski_sum()
) or as set-theoretic intersection via\[X \ominus Y = (X^c \oplus Y)^c = \cap_{y\in Y} (X-y)\]where superscript-“c” means the complement in the ambient vector space. The Minkowski difference of convex sets is convex, and the difference of polyhedra is again a polyhedron. We only consider the case of polyhedra in the following. Note that it is not quite the inverse of addition. In fact:
\((X+Y)-Y = X\) for any polyhedra \(X\), \(Y\).
\((X-Y)+Y \subseteq X\)
\((X-Y)+Y = X\) if and only if Y is a Minkowski summand of X.
INPUT:
other
– 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
The polyhedra need not be full-dimensional:
sage: X2 = Polyhedron(vertices=[(-1,-1,0),(1,-1,0),(-1,1,0),(1,1,0)]) sage: Y2 = Polyhedron(vertices=[(0,0,0), (0,1,0), (1,0,0)]) / 2 sage: (X2+Y2)-Y2 == X2 True sage: (X2-Y2)+Y2 < X2 True
Minus sign is really an alias for
minkowski_difference()
sage: four_cube = polytopes.hypercube(4) sage: four_simplex = Polyhedron(vertices = [[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]) sage: four_cube - four_simplex A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 16 vertices sage: four_cube.minkowski_difference(four_simplex) == four_cube - four_simplex True
Coercion of the base ring works:
sage: poly_spam = Polyhedron([[3,4,5,2],[1,0,0,1],[0,0,0,0],[0,4,3,2],[-3,-3,-3,-3]], base_ring=ZZ) sage: poly_eggs = Polyhedron([[5,4,5,4],[-4,5,-4,5],[4,-5,4,-5],[0,0,0,0]], base_ring=QQ) / 100 sage: poly_spam - poly_eggs A 4-dimensional polyhedron in QQ^4 defined as the convex hull of 5 vertices
- minkowski_sum(other)¶
Return the Minkowski sum.
Minkowski addition of two subsets of a vector space is defined as
\[X \oplus Y = \cup_{y\in Y} (X+y) = \cup_{x\in X, y\in Y} (x+y)\]See
minkowski_difference()
for a partial inverse operation.INPUT:
other
– 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
- normal_fan(direction='inner')¶
Return the normal fan of a compact full-dimensional rational polyhedron.
This returns the inner normal fan of
self
. For the outer normal fan, usedirection='outer'
.INPUT:
direction
– either'inner'
(default) or'outer'
; if set to'inner'
, use the inner normal vectors to span the cones of the fan, if set to'outer'
, use the outer normal vectors.
OUTPUT:
A complete fan of the ambient space as a
RationalPolyhedralFan
.See also
EXAMPLES:
sage: S = Polyhedron(vertices = [[0, 0], [1, 0], [0, 1]]) sage: S.normal_fan() Rational polyhedral fan in 2-d lattice N sage: C = polytopes.hypercube(4) sage: NF = C.normal_fan(); NF Rational polyhedral fan in 4-d lattice N
Currently, it is only possible to get the normal fan of a bounded rational polytope:
sage: P = Polyhedron(rays = [[1, 0], [0, 1]]) sage: P.normal_fan() Traceback (most recent call last): ... NotImplementedError: the normal fan is only supported for polytopes (compact polyhedra). sage: Q = Polyhedron(vertices = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]) sage: Q.normal_fan() Traceback (most recent call last): ... ValueError: the normal fan is only defined for full-dimensional polytopes sage: R = Polyhedron(vertices = [[0, 0], [AA(sqrt(2)), 0], [0, AA(sqrt(2))]]) sage: R.normal_fan() Traceback (most recent call last): ... NotImplementedError: normal fan handles only polytopes over the rationals sage: P = Polyhedron(vertices=[[0,0],[2,0],[0,2],[2,1],[1,2]]) sage: P.normal_fan(direction=None) Traceback (most recent call last): ... TypeError: the direction should be 'inner' or 'outer' sage: inner_nf = P.normal_fan() sage: inner_nf.rays() N( 1, 0), N( 0, -1), N( 0, 1), N(-1, 0), N(-1, -1) in 2-d lattice N sage: outer_nf = P.normal_fan(direction='outer') sage: outer_nf.rays() N( 1, 0), N( 1, 1), N( 0, 1), N(-1, 0), N( 0, -1) in 2-d lattice N
REFERENCES:
For more information, see Chapter 7 of [Zie2007].
- one_point_suspension(vertex)¶
Return the one-point suspension of
self
by splitting the vertexvertex
.The resulting polyhedron has one more vertex and its dimension increases by one.
INPUT:
vertex
– a Vertex ofself
EXAMPLES:
sage: cube = polytopes.cube() sage: v = cube.vertices()[0] sage: ops_cube = cube.one_point_suspension(v) sage: ops_cube.f_vector() (1, 9, 24, 24, 9, 1) sage: pentagon = polytopes.regular_polygon(5) # optional - sage.rings.number_field sage: v = pentagon.vertices()[0] # optional - sage.rings.number_field sage: ops_pentagon = pentagon.one_point_suspension(v) # optional - sage.rings.number_field sage: ops_pentagon.f_vector() # optional - sage.rings.number_field (1, 6, 12, 8, 1)
It works with a polyhedral face as well:
sage: vv = cube.faces(0)[1] sage: ops_cube2 = cube.one_point_suspension(vv) sage: ops_cube == ops_cube2 True
See also
- plot(point=None, line=None, polygon=None, wireframe='blue', fill='green', position=None, orthonormal=True, **kwds)¶
Return a graphical representation.
INPUT:
point
,line
,polygon
– Parameters to pass to point (0d), line (1d), and polygon (2d) plot commands. Allowed values are:A Python dictionary to be passed as keywords to the plot commands.
A string or triple of numbers: The color. This is equivalent to passing the dictionary
{'color':...}
.False
: Switches off the drawing of the corresponding graphics object
wireframe
,fill
– Similar topoint
,line
, andpolygon
, butfill
is used for the graphics objects in the dimension of the polytope (or of dimension 2 for higher dimensional polytopes) andwireframe
is used for all lower-dimensional graphics objects (default: ‘green’ forfill
and ‘blue’ forwireframe
)position
– positive number; the position to take the projection point in Schlegel diagrams.orthonormal
– Boolean (default: True); whether to use orthonormal projections.**kwds
– optional keyword parameters that are passed to all graphics objects.
OUTPUT:
A (multipart) graphics object.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: point = Polyhedron([[1,1]]) sage: line = Polyhedron([[1,1],[2,1]]) sage: cube = polytopes.hypercube(3) sage: hypercube = polytopes.hypercube(4)
By default, the wireframe is rendered in blue and the fill in green:
sage: square.plot() # optional - sage.plot Graphics object consisting of 6 graphics primitives sage: point.plot() # optional - sage.plot Graphics object consisting of 1 graphics primitive sage: line.plot() # optional - sage.plot Graphics object consisting of 2 graphics primitives sage: cube.plot() # optional - sage.plot Graphics3d Object sage: hypercube.plot() # optional - sage.plot Graphics3d Object
Draw the lines in red and nothing else:
sage: square.plot(point=False, line='red', polygon=False) # optional - sage.plot Graphics object consisting of 4 graphics primitives sage: point.plot(point=False, line='red', polygon=False) # optional - sage.plot Graphics object consisting of 0 graphics primitives sage: line.plot(point=False, line='red', polygon=False) # optional - sage.plot Graphics object consisting of 1 graphics primitive sage: cube.plot(point=False, line='red', polygon=False) # optional - sage.plot Graphics3d Object sage: hypercube.plot(point=False, line='red', polygon=False) # optional - sage.plot Graphics3d Object
Draw points in red, no lines, and a blue polygon:
sage: square.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) # optional - sage.plot Graphics object consisting of 2 graphics primitives sage: point.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) # optional - sage.plot Graphics object consisting of 1 graphics primitive sage: line.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) # optional - sage.plot Graphics object consisting of 1 graphics primitive sage: cube.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) # optional - sage.plot Graphics3d Object sage: hypercube.plot(point={'color':'red'}, line=False, polygon=(0,0,1)) # optional - sage.plot Graphics3d Object
If we instead use the
fill
andwireframe
options, the coloring depends on the dimension of the object:sage: square.plot(fill='green', wireframe='red') # optional - sage.plot Graphics object consisting of 6 graphics primitives sage: point.plot(fill='green', wireframe='red') # optional - sage.plot Graphics object consisting of 1 graphics primitive sage: line.plot(fill='green', wireframe='red') # optional - sage.plot Graphics object consisting of 2 graphics primitives sage: cube.plot(fill='green', wireframe='red') # optional - sage.plot Graphics3d Object sage: hypercube.plot(fill='green', wireframe='red') # optional - sage.plot Graphics3d Object
It is possible to draw polyhedra up to dimension 4, no matter what the ambient dimension is:
sage: hcube = polytopes.hypercube(5) sage: facet = hcube.facets()[0].as_polyhedron();facet A 4-dimensional polyhedron in ZZ^5 defined as the convex hull of 16 vertices sage: facet.plot() # optional - sage.plot Graphics3d Object
- polar(in_affine_span=False)¶
Return the polar (dual) polytope.
The original vertices are translated so that their barycenter is at the origin, and then the vertices are used as the coefficients in the polar inequalities.
The polytope must be full-dimensional, unless
in_affine_span
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) sage: p A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices sage: p.polar() A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 6 vertices sage: cube = polytopes.hypercube(3) sage: octahedron = polytopes.cross_polytope(3) sage: cube_dual = cube.polar() sage: octahedron == cube_dual True
in_affine_span
somewhat ignores equations, performing the polar in the spanned subspace (after translating barycenter to origin):sage: P = polytopes.simplex(3, base_ring=QQ) sage: P.polar(in_affine_span=True) A 3-dimensional polyhedron in QQ^4 defined as the convex hull of 4 vertices
Embedding the polytope in a higher dimension, commutes with polar in this case:
sage: point = Polyhedron([[0]]) sage: P = polytopes.cube().change_ring(QQ) sage: (P*point).polar(in_affine_span=True) == P.polar()*point True
- prism()¶
Return a prism of the original polyhedron.
EXAMPLES:
sage: square = polytopes.hypercube(2) sage: cube = square.prism() sage: cube A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices sage: hypercube = cube.prism() sage: hypercube.n_vertices() 16
- product(other)¶
Return the Cartesian product.
INPUT:
other
– 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
The Cartesian product is the product in the semiring of polyhedra:
sage: P1 * P1 A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: P1 * P2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: P2 * P2 A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: 2 * P1 A 1-dimensional polyhedron in ZZ^1 defined as the convex hull of 2 vertices sage: P1 * 2.0 A 1-dimensional polyhedron in RDF^1 defined as the convex hull of 2 vertices
An alias is
cartesian_product()
:sage: P1.cartesian_product(P2) == P1.product(P2) True
- projection(projection=None)¶
Return a projection object.
INPUT:
proj
– a projection function
OUTPUT:
The identity projection. This is useful for plotting polyhedra.
See also
schlegel_projection()
for a more interesting projection.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: proj = p.projection() sage: proj The projection of a polyhedron into 3 dimensions
- pyramid()¶
Return a polyhedron that is a pyramid over the original.
EXAMPLES:
sage: square = polytopes.hypercube(2); square A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices sage: egyptian_pyramid = square.pyramid(); egyptian_pyramid A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices sage: egyptian_pyramid.n_vertices() 5 sage: for v in egyptian_pyramid.vertex_generator(): print(v) A vertex at (0, -1, -1) A vertex at (0, -1, 1) A vertex at (0, 1, -1) A vertex at (0, 1, 1) A vertex at (1, 0, 0)
- radius()¶
Return the maximal distance from the center to a vertex. All rays and lines are ignored.
OUTPUT:
The radius for a rational polyhedron is, in general, not rational. use
radius_square()
if you need a rational distance measure.EXAMPLES:
sage: p = polytopes.hypercube(4) sage: p.radius() 2
- radius_square()¶
Return the square of the maximal distance from the
center()
to a vertex. All rays and lines are ignored.OUTPUT:
The square of the radius, which is in
base_ring()
.EXAMPLES:
sage: p = polytopes.permutahedron(4, project = False) sage: p.radius_square() 5
- render_solid(**kwds)¶
Return a solid rendering of a 2- or 3-d polytope.
EXAMPLES:
sage: p = polytopes.hypercube(3) sage: p_solid = p.render_solid(opacity = .7) sage: type(p_solid) <class 'sage.plot.plot3d.index_face_set.IndexFaceSet'>
- render_wireframe(**kwds)¶
For polytopes in 2 or 3 dimensions, return the edges as a list of lines.
EXAMPLES:
sage: p = Polyhedron([[1,2,],[1,1],[0,0]]) sage: p_wireframe = p.render_wireframe() sage: p_wireframe._objects [Line defined by 2 points, Line defined by 2 points, Line defined by 2 points]
- schlegel_projection(facet=None, position=None)¶
Return the Schlegel projection.
The facet is orthonormally transformed into its affine hull.
The position specifies a point coming out of the barycenter of the facet from which the other vertices will be projected into the facet.
INPUT:
facet
– a PolyhedronFace. The facet into which the Schlegel diagram is created. The default is the first facet.position
– a positive number. Determines a relative distance from the barycenter offacet
. A value close to 0 will place the projection point close to the facet and a large value further away. Default is \(1\). If the given value is too large, an error is returned.
OUTPUT:
A
Projection
object.EXAMPLES:
sage: p = polytopes.hypercube(3) sage: sch_proj = p.schlegel_projection() sage: schlegel_edge_indices = sch_proj.lines sage: schlegel_edges = [sch_proj.coordinates_of(x) for x in schlegel_edge_indices] sage: len([x for x in schlegel_edges if x[0][0] > 0]) 8
The Schlegel projection preserves the convexity of facets, see trac ticket #30015:
sage: fcube = polytopes.hypercube(4) sage: tfcube = fcube.face_truncation(fcube.faces(0)[0]) sage: tfcube.facets()[-1] A 3-dimensional face of a Polyhedron in QQ^4 defined as the convex hull of 8 vertices sage: sp = tfcube.schlegel_projection(tfcube.facets()[-1]) sage: sp.plot() # optional - sage.plot Graphics3d Object
The same truncated cube but see inside the tetrahedral facet:
sage: tfcube.facets()[4] A 3-dimensional face of a Polyhedron in QQ^4 defined as the convex hull of 4 vertices sage: sp = tfcube.schlegel_projection(tfcube.facets()[4]) sage: sp.plot() # optional - sage.plot Graphics3d Object
A different values of
position
changes the projection:sage: sp = tfcube.schlegel_projection(tfcube.facets()[4],1/2) sage: sp.plot() # optional - sage.plot Graphics3d Object sage: sp = tfcube.schlegel_projection(tfcube.facets()[4],4) sage: sp.plot() # optional - sage.plot Graphics3d Object
A value which is too large give a projection point that sees more than one facet resulting in a error:
sage: sp = tfcube.schlegel_projection(tfcube.facets()[4],5) Traceback (most recent call last): ... ValueError: the chosen position is too large
- show(**kwds)¶
Display graphics immediately
This method attempts to display the graphics immediately, without waiting for the currently running code (if any) to return to the command line. Be careful, calling it from within a loop will potentially launch a large number of external viewer programs.
INPUT:
kwds
– optional keyword arguments. Seeplot()
for the description of available options.
OUTPUT:
This method does not return anything. Use
plot()
if you want to generate a graphics object that can be saved or further transformed.EXAMPLES:
sage: square = polytopes.hypercube(2) sage: square.show(point='red')
- stack(face, position=None)¶
Return a new polyhedron formed by stacking onto a
face
. Stacking a face adds a new vertex located slightly outside of the designated face.INPUT:
face
– a 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: hexaprism = polytopes.regular_polygon(6).prism() # optional - sage.rings.number_field sage: hexaprism.f_vector() # optional - sage.rings.number_field (1, 12, 18, 8, 1) sage: square_face = hexaprism.faces(2)[2] # optional - sage.rings.number_field sage: stacked_hexaprism = hexaprism.stack(square_face) # optional - sage.rings.number_field sage: stacked_hexaprism.f_vector() # optional - sage.rings.number_field (1, 13, 22, 11, 1) sage: hexaprism.stack(square_face,position=4) # optional - 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))
It is possible to stack on unbounded faces:
sage: Q = Polyhedron(vertices=[[0,1],[1,0]],rays=[[1,1]]) sage: E = Q.faces(1) sage: Q.stack(E[0],1/2).Vrepresentation() (A vertex at (0, 1), A vertex at (1, 0), A ray in the direction (1, 1), A vertex at (2, 0)) sage: Q.stack(E[1],1/2).Vrepresentation() (A vertex at (0, 1), A vertex at (0, 2), A vertex at (1, 0), A ray in the direction (1, 1)) sage: Q.stack(E[2],1/2).Vrepresentation() (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A ray in the direction (1, 1))
Stacking requires a proper face:
sage: Q.stack(Q.faces(2)[0]) Traceback (most recent call last): ... ValueError: can only stack on proper face
- subdirect_sum(other)¶
Return the subdirect sum of
self
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))
See also
- tikz(view=[0, 0, 1], angle=0, scale=1, edge_color='blue!95!black', facet_color='blue!95!black', opacity=0.8, vertex_color='green', axis=False)¶
Return a string
tikz_pic
consisting of a tikz picture ofself
according to a projectionview
and an angleangle
obtained via the threejs viewer.INPUT:
view
- list (default: [0,0,1]) representing the rotation axis (see note below).angle
- integer (default: 0) angle of rotation in degree from 0 to 360 (see note below).scale
- integer (default: 1) specifying the scaling of the tikz picture.edge_color
- string (default: ‘blue!95!black’) representing colors which tikz recognize.facet_color
- string (default: ‘blue!95!black’) representing colors which tikz recognize.vertex_color
- string (default: ‘green’) representing colors which tikz recognize.opacity
- real number (default: 0.8) between 0 and 1 giving the opacity of the front facets.axis
- Boolean (default: False) draw the axes at the origin or not.
OUTPUT:
LatexExpr – containing the TikZ picture.
Note
This is a wrapper of a method of the projection object \(self.projection()\). See
tikz()
for more detail.The inputs
view
andangle
can be obtained by visualizing it using.show(aspect_ratio=1)
. This will open an interactive view in your default browser, where you can rotate the polytope. Once the desired view angle is found, click on the information icon in the lower right-hand corner and select Get Viewpoint. This will copy a string of the form ‘[x,y,z],angle’ to your local clipboard. Go back to Sage and typeImg = P.tikz([x,y,z],angle)
.The inputs
view
andangle
can also be obtained from the viewer Jmol:1) Right click on the image 2) Select ``Console`` 3) Select the tab ``State`` 4) Scroll to the line ``moveto``
It reads something like:
moveto 0.0 {x y z angle} Scale
The
view
is then [x,y,z] andangle
is angle. The following number is the scale.Jmol performs a rotation of
angle
degrees along the vector [x,y,z] and show the result from the z-axis.EXAMPLES:
sage: co = polytopes.cuboctahedron() sage: Img = co.tikz([0,0,1], 0) sage: print('\n'.join(Img.splitlines()[:9])) \begin{tikzpicture}% [x={(1.000000cm, 0.000000cm)}, y={(0.000000cm, 1.000000cm)}, z={(0.000000cm, 0.000000cm)}, scale=1.000000, back/.style={loosely dotted, thin}, edge/.style={color=blue!95!black, thick}, facet/.style={fill=blue!95!black,fill opacity=0.800000}, vertex/.style={inner sep=1pt,circle,draw=green!25!black,fill=green!75!black,thick}] sage: print('\n'.join(Img.splitlines()[12:21])) %% with the command: ._tikz_3d_in_3d and parameters: %% view = [0, 0, 1] %% angle = 0 %% scale = 1 %% edge_color = blue!95!black %% facet_color = blue!95!black %% opacity = 0.8 %% vertex_color = green %% axis = False sage: print('\n'.join(Img.splitlines()[22:26])) %% Coordinate of the vertices: %% \coordinate (-1.00000, -1.00000, 0.00000) at (-1.00000, -1.00000, 0.00000); \coordinate (-1.00000, 0.00000, -1.00000) at (-1.00000, 0.00000, -1.00000);
- to_linear_program(solver=None, return_variable=False, base_ring=None)¶
Return a linear optimization problem over the polyhedron in the form of a
MixedIntegerLinearProgram
.INPUT:
solver
– select a solver (MIP backend). See the documentation of forMixedIntegerLinearProgram
. Set toNone
by default.return_variable
– (default:False
) IfTrue
, return a tuple(p, x)
, wherep
is theMixedIntegerLinearProgram
object andx
is the vector-valued MIP variable in this problem, indexed from 0. IfFalse
, only returnp
.base_ring
– select a field over which the linear program should be set up. UseRDF
to request a fast inexact (floating point) solver even ifself
is exact.
Note that the
MixedIntegerLinearProgram
object will have the null function as an objective to be maximized.See also
polyhedron()
– return the polyhedron associated with aMixedIntegerLinearProgram
object.EXAMPLES:
Exact rational linear program:
sage: p = polytopes.cube() sage: p.to_linear_program() Linear Program (no objective, 3 variables, 6 constraints) sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(2*x[0] + 1*x[1] + 39*x[2]) sage: lp.solve() 42 sage: lp.get_values(x[0], x[1], x[2]) [1, 1, 1]
Floating-point linear program:
sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF) sage: lp.set_objective(2*x[0] + 1*x[1] + 39*x[2]) sage: lp.solve() 42.0
Irrational algebraic linear program over an embedded number field:
sage: p=polytopes.icosahedron() sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() 1/4*sqrt5 + 3/4
Same example with floating point:
sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # tol 1e-5 1.3090169943749475
Same example with a specific floating point solver:
sage: lp, x = p.to_linear_program(return_variable=True, solver='GLPK') sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # tol 1e-8 1.3090169943749475
Irrational algebraic linear program over \(AA\):
sage: p=polytopes.icosahedron(base_ring=AA) sage: lp, x = p.to_linear_program(return_variable=True) sage: lp.set_objective(x[0] + x[1] + x[2]) sage: lp.solve() # long time 1.309016994374948?
- translation(displacement)¶
Return the translated polyhedron.
INPUT:
displacement
– a displacement vector or a list/tuple of coordinates that determines a displacement vector
OUTPUT:
The translated polyhedron.
EXAMPLES:
sage: P = Polyhedron([[0,0],[1,0],[0,1]], base_ring=ZZ) sage: P.translation([2,1]) A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: P.translation( vector(QQ,[2,1]) ) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 3 vertices
- triangulate(engine='auto', connected=True, fine=False, regular=None, star=None)¶
Return a triangulation of the polytope.
INPUT:
engine
– either ‘auto’ (default), ‘internal’, ‘TOPCOM’, or ‘normaliz’. The ‘internal’ and ‘TOPCOM’ instruct this package to always use its own triangulation algorithms or TOPCOM’s algorithms, respectively. By default (‘auto’), TOPCOM is used if it is available and internal routines otherwise.
The remaining keyword parameters are passed through to the
PointConfiguration
constructor:connected
– boolean (default:True
). Whether the triangulations should be connected to the regular triangulations via bistellar flips. These are much easier to compute than all triangulations.fine
– boolean (default:False
). Whether the triangulations must be fine, that is, make use of all points of the configuration.regular
– boolean orNone
(default:None
). Whether the triangulations must be regular. A regular triangulation is one that is induced by a piecewise-linear convex support function. In other words, the shadows of the faces of a polyhedron in one higher dimension.True
: Only regular triangulations.False
: Only non-regular triangulations.None
(default): Both kinds of triangulation.
star
– eitherNone
(default) or a point. Whether the triangulations must be star. A triangulation is star if all maximal simplices contain a common point. The central point can be specified by its index (an integer) in the given points or by its coordinates (anything iterable.)
OUTPUT:
A triangulation of the convex hull of the vertices as a
Triangulation
. The indices in the triangulation correspond to theVrepresentation()
objects.EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: triangulation = cube.triangulate( ....: engine='internal') # to make doctest independent of TOPCOM sage: triangulation (<0,1,2,7>, <0,1,5,7>, <0,2,3,7>, <0,3,4,7>, <0,4,5,7>, <1,5,6,7>) sage: simplex_indices = triangulation[0]; simplex_indices (0, 1, 2, 7) sage: simplex_vertices = [ cube.Vrepresentation(i) for i in simplex_indices ] sage: simplex_vertices [A vertex at (1, -1, -1), A vertex at (1, 1, -1), A vertex at (1, 1, 1), A vertex at (-1, 1, 1)] sage: Polyhedron(simplex_vertices) A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
It is possible to use
'normaliz'
as an engine. For this, the polyhedron should have the backend set to normaliz:sage: P = Polyhedron(vertices=[[0,0,1],[1,0,1],[0,1,1],[1,1,1]],backend='normaliz') # optional - pynormaliz sage: P.triangulate(engine='normaliz') # optional - pynormaliz (<0,1,2>, <1,2,3>) sage: P = Polyhedron(vertices=[[0,0,1],[1,0,1],[0,1,1],[1,1,1]]) sage: P.triangulate(engine='normaliz') Traceback (most recent call last): ... TypeError: the polyhedron's backend should be 'normaliz'
The normaliz engine can triangulate pointed cones:
sage: C1 = Polyhedron(rays=[[0,0,1],[1,0,1],[0,1,1],[1,1,1]],backend='normaliz') # optional - pynormaliz sage: C1.triangulate(engine='normaliz') # optional - pynormaliz (<0,1,2>, <1,2,3>) sage: C2 = Polyhedron(rays=[[1,0,1],[0,0,1],[0,1,1],[1,1,10/9]],backend='normaliz') # optional - pynormaliz sage: C2.triangulate(engine='normaliz') # optional - pynormaliz (<0,1,2>, <1,2,3>)
They can also be affine cones:
sage: K = Polyhedron(vertices=[[1,1,1]],rays=[[1,0,0],[0,1,0],[1,1,-1],[1,1,1]], backend='normaliz') # optional - pynormaliz sage: K.triangulate(engine='normaliz') # optional - pynormaliz (<0,1,2>, <0,1,3>)
- truncation(cut_frac=None)¶
Return a new polyhedron formed from two points on each edge between two vertices.
INPUT:
cut_frac
– integer, how deeply to cut into the edge. Default is \(\frac{1}{3}\).
OUTPUT:
A Polyhedron object, truncated as described above.
EXAMPLES:
sage: cube = polytopes.hypercube(3) sage: trunc_cube = cube.truncation() sage: trunc_cube.n_vertices() 24 sage: trunc_cube.n_inequalities() 14
- volume(measure='ambient', engine='auto', **kwds)¶
Return the volume of the polytope.
INPUT:
measure
– string. The measure to use. Allowed values are:ambient
(default): Lebesgue measure of ambient space (volume)induced
: Lebesgue measure of the affine hull (relative volume)induced_rational
: Scaling of the Lebesgue measure for rational polytopes, such that the unit hypercube has volume 1induced_lattice
: Scaling of the Lebesgue measure, such that the volume of the hypercube is factorial(n)
engine
– string. The backend to use. Allowed values are:'auto'
(default): choose engine according to measure'internal'
: seetriangulate()
'TOPCOM'
: seetriangulate()
'lrs'
: use David Avis’s lrs program (optional)'latte'
: use LattE integrale program (optional)'normaliz'
: use Normaliz program (optional)
**kwds
– keyword arguments that are passed to the triangulation engine
OUTPUT:
The volume of the polytope
EXAMPLES:
sage: polytopes.hypercube(3).volume() 8 sage: (polytopes.hypercube(3)*2).volume() 64 sage: polytopes.twenty_four_cell().volume() 2
Volume of the same polytopes, using the optional package lrslib (which requires a rational polytope). For mysterious historical reasons, Sage casts lrs’s exact answer to a float:
sage: I3 = polytopes.hypercube(3) sage: I3.volume(engine='lrs') # optional - lrslib 8.0 sage: C24 = polytopes.twenty_four_cell() sage: C24.volume(engine='lrs') # optional - lrslib 2.0
If the base ring is exact, the answer is exact:
sage: P5 = polytopes.regular_polygon(5) # optional - sage.rings.number_field sage: P5.volume() # optional - sage.rings.number_field 2.377641290737884? sage: polytopes.icosahedron().volume() # optional - sage.rings.number_field 5/12*sqrt5 + 5/4 sage: numerical_approx(_) # abs tol 1e9 # optional - sage.rings.number_field 2.18169499062491
When considering lower-dimensional polytopes, we can ask for the ambient (full-dimensional), the induced measure (of the affine hull) or, in the case of lattice polytopes, for the induced rational measure. This is controlled by the parameter \(measure\). Different engines may have different ideas on the definition of volume of a lower-dimensional object:
sage: P = Polyhedron([[0, 0], [1, 1]]) sage: P.volume() 0 sage: P.volume(measure='induced') 1.414213562373095? sage: P.volume(measure='induced_rational') # optional -- latte_int 1 sage: S = polytopes.regular_polygon(6); S # optional - sage.rings.number_field A 2-dimensional polyhedron in AA^2 defined as the convex hull of 6 vertices sage: edge = S.faces(1)[4].as_polyhedron() # optional - sage.rings.number_field sage: edge.vertices() # optional - sage.rings.number_field (A vertex at (0.866025403784439?, 1/2), A vertex at (0, 1)) sage: edge.volume() # optional - sage.rings.number_field 0 sage: edge.volume(measure='induced') # optional - sage.rings.number_field 1 sage: P = Polyhedron(backend='normaliz',vertices=[[1,0,0],[0,0,1],[-1,1,1],[-1,2,0]]) # optional - pynormaliz sage: P.volume() # optional - pynormaliz 0 sage: P.volume(measure='induced') # optional - pynormaliz # optional - sage.rings.number_field 2.598076211353316? sage: P.volume(measure='induced',engine='normaliz') # optional - pynormaliz 2.598076211353316 sage: P.volume(measure='induced_rational') # optional - pynormaliz, latte_int 3/2 sage: P.volume(measure='induced_rational',engine='normaliz') # optional - pynormaliz 3/2 sage: P.volume(measure='induced_lattice') # optional - pynormaliz 3
The same polytope without normaliz backend:
sage: P = Polyhedron(vertices=[[1,0,0],[0,0,1],[-1,1,1],[-1,2,0]]) sage: P.volume(measure='induced_lattice',engine='latte') # optional - latte_int 3 sage: Dexact = polytopes.dodecahedron() # optional - sage.rings.number_field sage: v = Dexact.faces(2)[0].as_polyhedron().volume(measure='induced', engine='internal'); v # optional - sage.rings.number_field 1.53406271079097? sage: v = Dexact.faces(2)[4].as_polyhedron().volume(measure='induced', engine='internal'); v # optional - sage.rings.number_field 1.53406271079097? sage: RDF(v) # abs tol 1e-9 # optional - sage.rings.number_field 1.53406271079044 sage: Dinexact = polytopes.dodecahedron(exact=False) sage: w = Dinexact.faces(2)[2].as_polyhedron().volume(measure='induced', engine='internal'); RDF(w) # abs tol 1e-9 1.5340627082974878 sage: [polytopes.simplex(d).volume(measure='induced') for d in range(1,5)] == [sqrt(d+1)/factorial(d) for d in range(1,5)] True sage: I = Polyhedron([[-3, 0], [0, 9]]) sage: I.volume(measure='induced') # optional - sage.rings.number_field 9.48683298050514? sage: I.volume(measure='induced_rational') # optional -- latte_int 3 sage: T = Polyhedron([[3, 0, 0], [0, 4, 0], [0, 0, 5]]) sage: T.volume(measure='induced') # optional - sage.rings.number_field 13.86542462386205? sage: T.volume(measure='induced_rational') # optional -- latte_int 1/2 sage: Q = Polyhedron(vertices=[(0, 0, 1, 1), (0, 1, 1, 0), (1, 1, 0, 0)]) sage: Q.volume(measure='induced') 1 sage: Q.volume(measure='induced_rational') # optional -- latte_int 1/2
The volume of a full-dimensional unbounded polyhedron is infinity:
sage: P = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]]) sage: P.volume() +Infinity
The volume of a non full-dimensional unbounded polyhedron depends on the measure used:
sage: P = Polyhedron(ieqs = [[1,1,1],[-1,-1,-1],[3,1,0]]); P A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray sage: P.volume() 0 sage: P.volume(measure='induced') +Infinity sage: P.volume(measure='ambient') 0 sage: P.volume(measure='induced_rational') # optional - pynormaliz +Infinity sage: P.volume(measure='induced_rational',engine='latte') # optional - latte_int +Infinity
The volume in \(0\)-dimensional space is taken by counting measure:
sage: P = Polyhedron(vertices=[[]]); P A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex sage: P.volume() 1 sage: P = Polyhedron(vertices=[]); P The empty polyhedron in ZZ^0 sage: P.volume() 0
- wedge(face, width=1)¶
Return the wedge over a
face
of the 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: P_4 = polytopes.regular_polygon(4) # optional - sage.rings.number_field sage: W1 = P_4.wedge(P_4.faces(1)[0]); W1 # optional - sage.rings.number_field A 3-dimensional polyhedron in AA^3 defined as the convex hull of 6 vertices sage: triangular_prism = polytopes.regular_polygon(3).prism() # optional - sage.rings.number_field sage: W1.is_combinatorially_isomorphic(triangular_prism) # optional - sage.graphs # optional - sage.rings.number_field 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) # optional - sage.rings.number_field sage: W4 = P_6.wedge(P_6.faces(1)[0]) # optional - sage.rings.number_field sage: W4.is_combinatorially_isomorphic(C_3_7.polar()) # optional - sage.graphs # optional - sage.rings.number_field True
REFERENCES:
For more information, see Chapter 15 of [HoDaCG17].
- write_cdd_Hrepresentation(filename)¶
Export the polyhedron as a H-representation to a file.
INPUT:
filename
– the output file.
See also
cdd_Hrepresentation()
– return the H-representation of the polyhedron as a string.EXAMPLES:
sage: from sage.misc.temporary_file import tmp_filename sage: filename = tmp_filename(ext='.ext') sage: polytopes.cube().write_cdd_Hrepresentation(filename)
- write_cdd_Vrepresentation(filename)¶
Export the polyhedron as a V-representation to a file.
INPUT:
filename
– the output file.
See also
cdd_Vrepresentation()
– return the V-representation of the polyhedron as a string.EXAMPLES:
sage: from sage.misc.temporary_file import tmp_filename sage: filename = tmp_filename(ext='.ext') sage: polytopes.cube().write_cdd_Vrepresentation(filename)
- sage.geometry.polyhedron.base.is_Polyhedron(X)¶
Test whether
X
is a Polyhedron.INPUT:
X
– anything.
OUTPUT:
Boolean.
EXAMPLES:
sage: p = polytopes.hypercube(2) sage: from sage.geometry.polyhedron.base import is_Polyhedron sage: is_Polyhedron(p) True sage: is_Polyhedron(123456) False