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)[source]¶

Bases: Polyhedron_base7

Base class for Polyhedron objects.

INPUT:

parent – the parent, an instance of Polyhedra
Vrep – list [vertices, rays, lines] or None. The V-representation of the polyhedron; if None, the polyhedron is determined by the H-representation
Hrep – list [ieqs, eqns] or None. The H-representation of the polyhedron; if None, the polyhedron is determined by the V-representation
Vrep_minimal – (optional) see below
Hrep_minimal – (optional) see below
pref_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 and Hrep are provided, then Vrep_minimal and Hrep_minimal must be set to True.

barycentric_subdivision(subdivision_frac=None)[source]¶

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

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

Python

>>> from sage.all import *
>>> P = polytopes.hypercube(Integer(3))
>>> P.barycentric_subdivision()
A 3-dimensional polyhedron in QQ^3 defined as the convex hull
of 26 vertices
>>> P = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)],[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(0),Integer(1)]])
>>> P.barycentric_subdivision()
A 3-dimensional polyhedron in QQ^3 defined as the convex hull
of 14 vertices
>>> P = Polyhedron(vertices=[[Integer(0),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(1)],[Integer(1),Integer(0),Integer(0)]])
>>> P.barycentric_subdivision()
A 2-dimensional polyhedron in QQ^3 defined as the convex hull
of 6 vertices
>>> P = polytopes.regular_polygon(Integer(4), base_ring=QQ)                        # needs sage.rings.number_field
>>> P.barycentric_subdivision()                                           # needs sage.rings.number_field
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 8
vertices

Sage Live

P = polytopes.hypercube(3)
P.barycentric_subdivision()
P = Polyhedron(vertices=[[0,0,0],[0,1,0],[1,0,0],[0,0,1]])
P.barycentric_subdivision()
P = Polyhedron(vertices=[[0,1,0],[0,0,1],[1,0,0]])
P.barycentric_subdivision()
P = polytopes.regular_polygon(4, base_ring=QQ)                        # needs sage.rings.number_field
P.barycentric_subdivision()                                           # needs sage.rings.number_field

boundary_complex()[source]¶

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

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}

Python

>>> from sage.all import *
>>> # needs sage.graphs
>>> oc = polytopes.octahedron()
>>> sc_oc = oc.boundary_complex()
>>> fl_oc = oc.face_lattice()                                             # needs sage.combinat
>>> fl_sc = sc_oc.face_poset()                                            # needs sage.combinat
>>> [len(x) for x in fl_oc.level_sets()]                                  # needs sage.combinat
[1, 6, 12, 8, 1]
>>> [len(x) for x in fl_sc.level_sets()]                                  # needs sage.combinat
[6, 12, 8]
>>> sc_oc.euler_characteristic()
2
>>> sc_oc.homology()
{0: 0, 1: 0, 2: Z}

Sage Live

# needs sage.graphs
oc = polytopes.octahedron()
sc_oc = oc.boundary_complex()
fl_oc = oc.face_lattice()                                             # needs sage.combinat
fl_sc = sc_oc.face_poset()                                            # needs sage.combinat
[len(x) for x in fl_oc.level_sets()]                                  # needs sage.combinat
[len(x) for x in fl_sc.level_sets()]                                  # needs sage.combinat
sc_oc.euler_characteristic()
sc_oc.homology()

The polyhedron should be simplicial:

Sage

sage: c = polytopes.cube()
sage: c.boundary_complex()
Traceback (most recent call last):
...
NotImplementedError: this function is only implemented for simplicial polytopes

Python

>>> from sage.all import *
>>> c = polytopes.cube()
>>> c.boundary_complex()
Traceback (most recent call last):
...
NotImplementedError: this function is only implemented for simplicial polytopes

Sage Live

c = polytopes.cube()
c.boundary_complex()

bounding_box(integral=False, integral_hull=False)[source]¶

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); if True, return a box containing the integral points of the polytope, or None, None if it is known that the polytope has no integral points

OUTPUT:

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> Polyhedron([(Integer(1)/Integer(3),Integer(2)/Integer(3)), (Integer(2)/Integer(3), Integer(1)/Integer(3))]).bounding_box()
((1/3, 1/3), (2/3, 2/3))
>>> Polyhedron([(Integer(1)/Integer(3),Integer(2)/Integer(3)), (Integer(2)/Integer(3), Integer(1)/Integer(3))]).bounding_box(integral=True)
((0, 0), (1, 1))
>>> Polyhedron([(Integer(1)/Integer(3),Integer(2)/Integer(3)), (Integer(2)/Integer(3), Integer(1)/Integer(3))]).bounding_box(integral_hull=True)
(None, None)
>>> Polyhedron([(Integer(1)/Integer(3),Integer(2)/Integer(3)), (Integer(3)/Integer(3), Integer(4)/Integer(3))]).bounding_box(integral_hull=True)
((1, 1), (1, 1))
>>> polytopes.buckyball(exact=False).bounding_box()                       # needs sage.groups
((-0.8090169944, -0.8090169944, -0.8090169944),
 (0.8090169944, 0.8090169944, 0.8090169944))

Sage Live

Polyhedron([(1/3,2/3), (2/3, 1/3)]).bounding_box()
Polyhedron([(1/3,2/3), (2/3, 1/3)]).bounding_box(integral=True)
Polyhedron([(1/3,2/3), (2/3, 1/3)]).bounding_box(integral_hull=True)
Polyhedron([(1/3,2/3), (3/3, 4/3)]).bounding_box(integral_hull=True)
polytopes.buckyball(exact=False).bounding_box()                       # needs sage.groups

center()[source]¶

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

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

Python

>>> from sage.all import *
>>> p = polytopes.hypercube(Integer(3))
>>> p = p + vector([Integer(1),Integer(0),Integer(0)])
>>> p.center()
(1, 0, 0)

Sage Live

p = polytopes.hypercube(3)
p = p + vector([1,0,0])
p.center()

face_fan()[source]¶

Return the face fan of a compact rational polyhedron.

OUTPUT:

A fan of the ambient space as a RationalPolyhedralFan.

See also

normal_fan().

EXAMPLES:

Sage

sage: T = polytopes.cuboctahedron()
sage: T.face_fan()
Rational polyhedral fan in 3-d lattice M

Python

>>> from sage.all import *
>>> T = polytopes.cuboctahedron()
>>> T.face_fan()
Rational polyhedral fan in 3-d lattice M

Sage Live

T = polytopes.cuboctahedron()
T.face_fan()

The polytope should contain the origin in the interior:

Sage

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

Python

>>> from sage.all import *
>>> P = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(1)], [Integer(1), Integer(1)/Integer(2)]])
>>> P.face_fan()
Traceback (most recent call last):
...
ValueError: face fans are defined only for polytopes
containing the origin as an interior point!

>>> Q = Polyhedron(vertices=[[-Integer(1), Integer(1)/Integer(2)], [Integer(1), -Integer(1)/Integer(2)]])
>>> Q.contains([Integer(0),Integer(0)])
True
>>> FF = Q.face_fan(); FF
Rational polyhedral fan in 2-d lattice M

Sage Live

P = Polyhedron(vertices=[[1/2, 1], [1, 1/2]])
P.face_fan()
Q = Polyhedron(vertices=[[-1, 1/2], [1, -1/2]])
Q.contains([0,0])
FF = Q.face_fan(); FF

The polytope has to have rational coordinates:

Sage

sage: S = polytopes.dodecahedron()                                          # needs sage.groups sage.rings.number_field
sage: S.face_fan()                                                          # needs sage.groups sage.rings.number_field
Traceback (most recent call last):
...
NotImplementedError: face fan handles only polytopes over the rationals

Python

>>> from sage.all import *
>>> S = polytopes.dodecahedron()                                          # needs sage.groups sage.rings.number_field
>>> S.face_fan()                                                          # needs sage.groups sage.rings.number_field
Traceback (most recent call last):
...
NotImplementedError: face fan handles only polytopes over the rationals

Sage Live

S = polytopes.dodecahedron()                                          # needs sage.groups sage.rings.number_field
S.face_fan()                                                          # needs sage.groups sage.rings.number_field

REFERENCES:

For more information, see Chapter 7 of [Zie2007].

hyperplane_arrangement()[source]¶

Return the hyperplane arrangement defined by the equations and inequalities.

OUTPUT:

A hyperplane arrangement consisting of the hyperplanes defined by the Hrepresentation(). If the polytope is full-dimensional, this is the hyperplane arrangement spanned by the facets of the polyhedron.

EXAMPLES:

Sage

sage: p = polytopes.hypercube(2)
sage: p.hyperplane_arrangement()
Arrangement <-t0 + 1 | -t1 + 1 | t1 + 1 | t0 + 1>

Python

>>> from sage.all import *
>>> p = polytopes.hypercube(Integer(2))
>>> p.hyperplane_arrangement()
Arrangement <-t0 + 1 | -t1 + 1 | t1 + 1 | t0 + 1>

Sage Live

p = polytopes.hypercube(2)
p.hyperplane_arrangement()

is_inscribed(certificate=False)[source]¶

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 – boolean (default: False); 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

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

Python

>>> from sage.all import *
>>> q = Polyhedron(vertices=[[Integer(1),Integer(1),Integer(1),Integer(1)],[-Integer(1),-Integer(1),Integer(1),Integer(1)],[Integer(1),-Integer(1),-Integer(1),Integer(1)],
...                            [-Integer(1),Integer(1),-Integer(1),Integer(1)],[Integer(1),Integer(1),Integer(1),-Integer(1)],[-Integer(1),-Integer(1),Integer(1),-Integer(1)],
...                            [Integer(1),-Integer(1),-Integer(1),-Integer(1)],[-Integer(1),Integer(1),-Integer(1),-Integer(1)],[Integer(0),Integer(0),Integer(10)/Integer(13),-Integer(24)/Integer(13)],
...                            [Integer(0),Integer(0),-Integer(10)/Integer(13),-Integer(24)/Integer(13)]])
>>> q.is_inscribed(certificate=True)
(True, (0, 0, 0, 0))

>>> cube = polytopes.cube()
>>> cube.is_inscribed()
True

>>> translated_cube = Polyhedron(vertices=[v.vector() + vector([Integer(1),Integer(2),Integer(3)])
...                                        for v in cube.vertices()])
>>> translated_cube.is_inscribed(certificate=True)
(True, (1, 2, 3))

>>> truncated_cube = cube.face_truncation(cube.faces(Integer(0))[Integer(0)])
>>> truncated_cube.is_inscribed()
False

Sage Live

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]])
q.is_inscribed(certificate=True)
cube = polytopes.cube()
cube.is_inscribed()
translated_cube = Polyhedron(vertices=[v.vector() + vector([1,2,3])
                                       for v in cube.vertices()])
translated_cube.is_inscribed(certificate=True)
truncated_cube = cube.face_truncation(cube.faces(0)[0])
truncated_cube.is_inscribed()

The method is not implemented for non-full-dimensional polytope or unbounded polyhedra:

Sage

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

Python

>>> from sage.all import *
>>> square = Polyhedron(vertices=[[Integer(1),Integer(0),Integer(0)],[Integer(0),Integer(1),Integer(0)],[Integer(1),Integer(1),Integer(0)],[Integer(0),Integer(0),Integer(0)]])
>>> square.is_inscribed()
Traceback (most recent call last):
...
NotImplementedError: this function is implemented for full-dimensional polyhedra only

>>> p = Polyhedron(vertices=[(Integer(0),Integer(0))],rays=[(Integer(1),Integer(0)),(Integer(0),Integer(1))])
>>> p.is_inscribed()
Traceback (most recent call last):
...
NotImplementedError: this function is not implemented for unbounded polyhedra

Sage Live

square = Polyhedron(vertices=[[1,0,0],[0,1,0],[1,1,0],[0,0,0]])
square.is_inscribed()
p = Polyhedron(vertices=[(0,0)],rays=[(1,0),(0,1)])
p.is_inscribed()

is_minkowski_summand(Y)[source]¶

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

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

Python

>>> from sage.all import *
>>> A = polytopes.hypercube(Integer(2))
>>> B = Polyhedron(vertices=[(Integer(0),Integer(1)), (Integer(1)/Integer(2),Integer(1))])
>>> C = Polyhedron(vertices=[(Integer(1),Integer(1))])
>>> A.is_minkowski_summand(B)
True
>>> A.is_minkowski_summand(C)
True
>>> B.is_minkowski_summand(C)
True
>>> B.is_minkowski_summand(A)
False
>>> C.is_minkowski_summand(A)
False
>>> C.is_minkowski_summand(B)
False

Sage Live

A = polytopes.hypercube(2)
B = Polyhedron(vertices=[(0,1), (1/2,1)])
C = Polyhedron(vertices=[(1,1)])
A.is_minkowski_summand(B)
A.is_minkowski_summand(C)
B.is_minkowski_summand(C)
B.is_minkowski_summand(A)
C.is_minkowski_summand(A)
C.is_minkowski_summand(B)

normal_fan(direction='inner')[source]¶

Return the normal fan of a compact full-dimensional rational polyhedron.

This returns the inner normal fan of self. For the outer normal fan, use direction='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

face_fan().

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> S = Polyhedron(vertices=[[Integer(0), Integer(0)], [Integer(1), Integer(0)], [Integer(0), Integer(1)]])
>>> S.normal_fan()
Rational polyhedral fan in 2-d lattice N

>>> C = polytopes.hypercube(Integer(4))
>>> NF = C.normal_fan(); NF
Rational polyhedral fan in 4-d lattice N

Sage Live

S = Polyhedron(vertices=[[0, 0], [1, 0], [0, 1]])
S.normal_fan()
C = polytopes.hypercube(4)
NF = C.normal_fan(); NF

Currently, it is only possible to get the normal fan of a bounded rational polytope:

Sage

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

Python

>>> from sage.all import *
>>> P = Polyhedron(rays=[[Integer(1), Integer(0)], [Integer(0), Integer(1)]])
>>> P.normal_fan()
Traceback (most recent call last):
...
NotImplementedError: the normal fan is only supported for polytopes (compact polyhedra).

>>> Q = Polyhedron(vertices=[[Integer(1), Integer(0), Integer(0)], [Integer(0), Integer(1), Integer(0)], [Integer(0), Integer(0), Integer(1)]])
>>> Q.normal_fan()
Traceback (most recent call last):
...
ValueError: the normal fan is only defined for full-dimensional polytopes

>>> R = Polyhedron(vertices=[[Integer(0), Integer(0)],                                      # needs sage.rings.number_field sage.symbolic
...                          [AA(sqrt(Integer(2))), Integer(0)],
...                          [Integer(0), AA(sqrt(Integer(2)))]])
>>> R.normal_fan()                                                        # needs sage.rings.number_field sage.symbolic
Traceback (most recent call last):
...
NotImplementedError: normal fan handles only polytopes over the rationals

>>> P = Polyhedron(vertices=[[Integer(0),Integer(0)], [Integer(2),Integer(0)], [Integer(0),Integer(2)], [Integer(2),Integer(1)], [Integer(1),Integer(2)]])
>>> P.normal_fan(direction=None)
Traceback (most recent call last):
...
TypeError: the direction should be 'inner' or 'outer'

>>> inner_nf = P.normal_fan()
>>> inner_nf.rays()
N( 1,  0),
N( 0, -1),
N( 0,  1),
N(-1,  0),
N(-1, -1)
in 2-d lattice N

>>> outer_nf = P.normal_fan(direction='outer')
>>> outer_nf.rays()
N( 1,  0),
N( 1,  1),
N( 0,  1),
N(-1,  0),
N( 0, -1)
in 2-d lattice N

Sage Live

P = Polyhedron(rays=[[1, 0], [0, 1]])
P.normal_fan()
Q = Polyhedron(vertices=[[1, 0, 0], [0, 1, 0], [0, 0, 1]])
Q.normal_fan()
R = Polyhedron(vertices=[[0, 0],                                      # needs sage.rings.number_field sage.symbolic
                         [AA(sqrt(2)), 0],
                         [0, AA(sqrt(2))]])
R.normal_fan()                                                        # needs sage.rings.number_field sage.symbolic
P = Polyhedron(vertices=[[0,0], [2,0], [0,2], [2,1], [1,2]])
P.normal_fan(direction=None)
inner_nf = P.normal_fan()
inner_nf.rays()
outer_nf = P.normal_fan(direction='outer')
outer_nf.rays()

REFERENCES:

For more information, see Chapter 7 of [Zie2007].

permutations_to_matrices(conj_class_reps, acting_group=None, additional_elts=None)[source]¶

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 in conj_class_reps. By default, the acting_group is the restricted_automorphism_group() of the polytope. Each element in additional_elts also becomes a key.

INPUT:

conj_class_reps – list; a list of representatives of the conjugacy classes of the acting_group
acting_group – a subgroup of polytope’s restricted_automorphism_group()
additional_elts – list (default: None); a subset of the restricted_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

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

Python

>>> from sage.all import *
>>> # optional - pynormaliz, needs sage.groups
>>> square = Polyhedron(vertices=[[Integer(1),Integer(1)], [-Integer(1),Integer(1)],
...                               [-Integer(1),-Integer(1)], [Integer(1),-Integer(1)]],
...                     backend='normaliz')
>>> square.vertices()
(A vertex at (-1, -1),
 A vertex at (-1, 1),
 A vertex at (1, -1),
 A vertex at (1, 1))
>>> aut_square = square.restricted_automorphism_group(output='permutation')
>>> conj_reps = aut_square.conjugacy_classes_representatives()
>>> gens_dict = square.permutations_to_matrices(conj_reps)
>>> rotation_180 = aut_square([(Integer(0),Integer(3)),(Integer(1),Integer(2))])
>>> rotation_180, gens_dict[rotation_180]
(
            [-1  0  0]
            [ 0 -1  0]
(0,3)(1,2), [ 0  0  1]
)

Sage Live

# optional - pynormaliz, needs sage.groups
square = Polyhedron(vertices=[[1,1], [-1,1],
                              [-1,-1], [1,-1]],
                    backend='normaliz')
square.vertices()
aut_square = square.restricted_automorphism_group(output='permutation')
conj_reps = aut_square.conjugacy_classes_representatives()
gens_dict = square.permutations_to_matrices(conj_reps)
rotation_180 = aut_square([(0,3),(1,2)])
rotation_180, gens_dict[rotation_180]

This example tests the functionality for additional elements:

Sage

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]

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.real_mpfr
>>> C = polytopes.cross_polytope(Integer(2))
>>> G = C.restricted_automorphism_group(output='permutation')
>>> conj_reps = G.conjugacy_classes_representatives()
>>> add_elt = G([(Integer(0), Integer(2), Integer(3), Integer(1))])
>>> dict = C.permutations_to_matrices(conj_reps,
...                                   additional_elts=[add_elt])
>>> dict[add_elt]
 [ 0  1  0]
 [-1  0  0]
 [ 0  0  1]

Sage Live

# needs sage.groups sage.rings.real_mpfr
C = polytopes.cross_polytope(2)
G = C.restricted_automorphism_group(output='permutation')
conj_reps = G.conjugacy_classes_representatives()
add_elt = G([(0, 2, 3, 1)])
dict = C.permutations_to_matrices(conj_reps,
                                  additional_elts=[add_elt])
dict[add_elt]

radius()[source]¶

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

sage: p = polytopes.hypercube(4)
sage: p.radius()
2

Python

>>> from sage.all import *
>>> p = polytopes.hypercube(Integer(4))
>>> p.radius()
2

Sage Live

p = polytopes.hypercube(4)
p.radius()

radius_square()[source]¶

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

sage: p = polytopes.permutahedron(4, project = False)
sage: p.radius_square()
5

Python

>>> from sage.all import *
>>> p = polytopes.permutahedron(Integer(4), project = False)
>>> p.radius_square()
5

Sage Live

p = polytopes.permutahedron(4, project = False)
p.radius_square()

to_linear_program(solver=None, return_variable=False, base_ring=None)[source]¶

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 for MixedIntegerLinearProgram. Set to None by default.
return_variable – boolean (default: False); if True, return a tuple (p, x), where p is the MixedIntegerLinearProgram object and x is the vector-valued MIP variable in this problem, indexed from 0. If False, only return p.
base_ring – select a field over which the linear program should be set up. Use RDF to request a fast inexact (floating point) solver even if self 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 a MixedIntegerLinearProgram object.

EXAMPLES:

Exact rational linear program:

Sage

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]

Python

>>> from sage.all import *
>>> p = polytopes.cube()
>>> p.to_linear_program()
Linear Program (no objective, 3 variables, 6 constraints)
>>> lp, x = p.to_linear_program(return_variable=True)
>>> lp.set_objective(Integer(2)*x[Integer(0)] + Integer(1)*x[Integer(1)] + Integer(39)*x[Integer(2)])
>>> lp.solve()
42
>>> lp.get_values(x[Integer(0)], x[Integer(1)], x[Integer(2)])
[1, 1, 1]

Sage Live

p = polytopes.cube()
p.to_linear_program()
lp, x = p.to_linear_program(return_variable=True)
lp.set_objective(2*x[0] + 1*x[1] + 39*x[2])
lp.solve()
lp.get_values(x[0], x[1], x[2])

Floating-point linear program:

Sage

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

Python

>>> from sage.all import *
>>> lp, x = p.to_linear_program(return_variable=True, base_ring=RDF)
>>> lp.set_objective(Integer(2)*x[Integer(0)] + Integer(1)*x[Integer(1)] + Integer(39)*x[Integer(2)])
>>> lp.solve()
42.0

Sage Live

lp, x = p.to_linear_program(return_variable=True, base_ring=RDF)
lp.set_objective(2*x[0] + 1*x[1] + 39*x[2])
lp.solve()

Irrational algebraic linear program over an embedded number field:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> p = polytopes.icosahedron()
>>> lp, x = p.to_linear_program(return_variable=True)
>>> lp.set_objective(x[Integer(0)] + x[Integer(1)] + x[Integer(2)])
>>> lp.solve()
1/4*sqrt5 + 3/4

Sage Live

# needs sage.groups sage.rings.number_field
p = polytopes.icosahedron()
lp, x = p.to_linear_program(return_variable=True)
lp.set_objective(x[0] + x[1] + x[2])
lp.solve()

Same example with floating point:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> lp, x = p.to_linear_program(return_variable=True, base_ring=RDF)
>>> lp.set_objective(x[Integer(0)] + x[Integer(1)] + x[Integer(2)])
>>> lp.solve()                                               # tol 1e-5
1.3090169943749475

Sage Live

# needs sage.groups sage.rings.number_field
lp, x = p.to_linear_program(return_variable=True, base_ring=RDF)
lp.set_objective(x[0] + x[1] + x[2])
lp.solve()                                               # tol 1e-5

Same example with a specific floating point solver:

Sage

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

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> lp, x = p.to_linear_program(return_variable=True, solver='GLPK')
>>> lp.set_objective(x[Integer(0)] + x[Integer(1)] + x[Integer(2)])
>>> lp.solve()                                               # tol 1e-8
1.3090169943749475

Sage Live

# needs sage.groups sage.rings.number_field
lp, x = p.to_linear_program(return_variable=True, solver='GLPK')
lp.set_objective(x[0] + x[1] + x[2])
lp.solve()                                               # tol 1e-8

Irrational algebraic linear program over $A A$ :

Sage

sage: # needs sage.groups 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?

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> p = polytopes.icosahedron(base_ring=AA)
>>> lp, x = p.to_linear_program(return_variable=True)
>>> lp.set_objective(x[Integer(0)] + x[Integer(1)] + x[Integer(2)])
>>> lp.solve()                    # long time
1.309016994374948?

Sage Live

# needs sage.groups sage.rings.number_field
p = polytopes.icosahedron(base_ring=AA)
lp, x = p.to_linear_program(return_variable=True)
lp.set_objective(x[0] + x[1] + x[2])
lp.solve()                    # long time

sage.geometry.polyhedron.base.is_Polyhedron(X)[source]¶

Test whether X is a Polyhedron.

INPUT:

X – anything

OUTPUT: boolean

EXAMPLES:

Sage

sage: p = polytopes.hypercube(2)
sage: from sage.geometry.polyhedron.base import is_Polyhedron
sage: is_Polyhedron(p)
doctest:warning...
DeprecationWarning: is_Polyhedron is deprecated, use isinstance instead
See https://github.com/sagemath/sage/issues/34307 for details.
True
sage: is_Polyhedron(123456)
False

Python

>>> from sage.all import *
>>> p = polytopes.hypercube(Integer(2))
>>> from sage.geometry.polyhedron.base import is_Polyhedron
>>> is_Polyhedron(p)
doctest:warning...
DeprecationWarning: is_Polyhedron is deprecated, use isinstance instead
See https://github.com/sagemath/sage/issues/34307 for details.
True
>>> is_Polyhedron(Integer(123456))
False

Sage Live

p = polytopes.hypercube(2)
from sage.geometry.polyhedron.base import is_Polyhedron
is_Polyhedron(p)
is_Polyhedron(123456)