Base class for polyhedra: Miscellaneous methods#
- class sage.geometry.polyhedron.base.Polyhedron_base(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)#
Bases:
Polyhedron_base7
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 ofVrep
orHrep
to pick this in case the backend cannot initialize from complete double descriptionmutable
– ignored
If both
Vrep
andHrep
are provided, thenVrep_minimal
andHrep_minimal
must be set toTrue
.- 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) # needs sage.rings.number_field sage: P.barycentric_subdivision() # needs sage.rings.number_field A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 8 vertices
- 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: # needs sage.graphs sage: oc = polytopes.octahedron() sage: sc_oc = oc.boundary_complex() sage: fl_oc = oc.face_lattice() # needs sage.combinat sage: fl_sc = sc_oc.face_poset() # needs sage.combinat sage: [len(x) for x in fl_oc.level_sets()] # needs sage.combinat [1, 6, 12, 8, 1] sage: [len(x) for x in fl_sc.level_sets()] # needs sage.combinat [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() # needs sage.groups ((-0.8090169944, -0.8090169944, -0.8090169944), (0.8090169944, 0.8090169944, 0.8090169944))
- center()#
Return the average of the vertices.
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)
- 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() # needs sage.rings.number_field sage: S.face_fan() # needs sage.rings.number_field Traceback (most recent call last): ... NotImplementedError: face fan handles only polytopes over the rationals
REFERENCES:
For more information, see Chapter 7 of [Zie2007].
- 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>
- 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
- 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], # needs sage.rings.number_field sage.symbolic ....: [AA(sqrt(2)), 0], ....: [0, AA(sqrt(2))]]) sage: R.normal_fan() # needs sage.rings.number_field sage.symbolic 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].
- permutations_to_matrices(conj_class_reps, acting_group=None, additional_elts=None)#
Return a dictionary between different representations of elements in the
acting_group
, with group elements represented as permutations of the vertices of this polytope (keys) or matrices (values).The dictionary has entries for the generators of the
acting_group
and the representatives of conjugacy classes inconj_class_reps
. By default, theacting_group
is therestricted_automorphism_group()
of the polytope. Each element inadditional_elts
also becomes a key.INPUT:
conj_class_reps
– list. A list of representatives of the conjugacy classes of theacting_group
.acting_group
– a subgroup of polytope’srestricted_automorphism_group()
.additional_elts
– list (default=None). A subset of therestricted_automorphism_group()
of the polytope expressed as permutations.
OUTPUT:
A dictionary between elements of the
acting_group
expressed as permutations (keys) and matrices (values).EXAMPLES:
This example shows the dictionary between permutations and matrices for the generators of the
restricted_automorphism_group
of the \(\pm 1\) 2-dimensional square. The permutations are written in terms of the vertices of the square:sage: # optional - pynormaliz, needs sage.groups sage: square = Polyhedron(vertices=[[1,1], [-1,1], ....: [-1,-1], [1,-1]], ....: backend='normaliz') sage: square.vertices() (A vertex at (-1, -1), A vertex at (-1, 1), A vertex at (1, -1), A vertex at (1, 1)) sage: aut_square = square.restricted_automorphism_group(output='permutation') sage: conj_reps = aut_square.conjugacy_classes_representatives() sage: gens_dict = square.permutations_to_matrices(conj_reps) sage: rotation_180 = aut_square([(0,3),(1,2)]) sage: rotation_180, gens_dict[rotation_180] ( [-1 0 0] [ 0 -1 0] (0,3)(1,2), [ 0 0 1] )
This example tests the functionality for additional elements:
sage: # needs sage.groups sage.rings.real_mpfr sage: C = polytopes.cross_polytope(2) sage: G = C.restricted_automorphism_group(output='permutation') sage: conj_reps = G.conjugacy_classes_representatives() sage: add_elt = G([(0, 2, 3, 1)]) sage: dict = C.permutations_to_matrices(conj_reps, ....: additional_elts=[add_elt]) sage: dict[add_elt] [ 0 1 0] [-1 0 0] [ 0 0 1]
- 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
- 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: # needs sage.rings.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 # needs sage.rings.number_field 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 # needs sage.rings.number_field 1.3090169943749475
Irrational algebraic linear program over \(AA\):
sage: # needs sage.rings.number_field 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?
- 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