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

• Vrep – a list [vertices, rays, lines] or None. The V-representation of the polyhedron. If None, the polyhedron is determined by the H-representation.

• Hrep – a 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)

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

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

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)

face_fan()

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: 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()                                # optional - sage.rings.number_field
sage: S.face_fan()                                                # optional - 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 the Hrepresentation(). 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:

1. Boolean.

2. 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, 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: 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))]])   # optional - sage.rings.number_field
sage: R.normal_fan()                                                          # optional - sage.rings.number_field
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 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: square = Polyhedron(vertices=[[1,1],[-1,1],[-1,-1],[1,-1]], backend='normaliz') # optional - pynormaliz
sage: square.vertices() # optional - pynormaliz
(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')       # optional - pynormaliz
sage: conj_reps = aut_square.conjugacy_classes_representatives()                      # optional - pynormaliz
sage: gens_dict = square.permutations_to_matrices(conj_reps);                         # optional - pynormaliz
sage: rotation_180 = aut_square([(0,3),(1,2)])                                        # optional - pynormaliz
sage: rotation_180,gens_dict[rotation_180]                                            # optional - pynormaliz
(
            [-1  0  0]
            [ 0 -1  0]
(0,3)(1,2), [ 0  0  1]
)

This example tests the functionality for additional elements:

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 for MixedIntegerLinearProgram. Set to None by default.

• return_variable – (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: 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()                                           # optional - sage.rings.number_field
sage: lp, x = p.to_linear_program(return_variable=True)                     # optional - sage.rings.number_field
sage: lp.set_objective(x[0] + x[1] + x[2])                                  # optional - sage.rings.number_field
sage: lp.solve()                                                            # optional - sage.rings.number_field
1/4*sqrt5 + 3/4

Same example with floating point:

sage: lp, x = p.to_linear_program(return_variable=True, base_ring=RDF)      # optional - sage.rings.number_field
sage: lp.set_objective(x[0] + x[1] + x[2])                                  # optional - sage.rings.number_field
sage: lp.solve()                                               # tol 1e-5   # optional - 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')      # optional - sage.rings.number_field
sage: lp.set_objective(x[0] + x[1] + x[2])                                  # optional - sage.rings.number_field
sage: lp.solve()                                               # tol 1e-8   # optional - sage.rings.number_field
1.3090169943749475

Irrational algebraic linear program over \(AA\):

sage: p = polytopes.icosahedron(base_ring=AA)                               # optional - sage.rings.number_field
sage: lp, x = p.to_linear_program(return_variable=True)                     # optional - sage.rings.number_field
sage: lp.set_objective(x[0] + x[1] + x[2])                                  # optional - sage.rings.number_field
sage: lp.solve()                                               # long time  # optional - sage.rings.number_field
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