This module is part of the python backend for polyhedra. It uses the
double description method for cones
double_description to find minimal
H/V-representations of polyhedra. The latter works with cones
only. This is sufficient to treat general polyhedra by the following
construction: Any polyhedron can be embedded in one dimension higher
in the hyperplane . The cone over the embedded
polyhedron will be called the homogenized cone in the
following. Conversely, intersecting the homogenized cone with the
hyperplane
gives you back the original polyhedron.
While slower than specialized C/C++ implementations, the implementation is general and works with any field in Sage that allows you to define polyhedra.
Note
If you just want polyhedra over arbitrary fields then you should just use the Polyhedron() constructor.
EXAMPLES:
sage: from sage.geometry.polyhedron.double_description_inhomogeneous ....: import Hrep2Vrep, Vrep2Hrep
sage: Hrep2Vrep(QQ, 2, [(1,2,3), (2,4,3)], [])
[-1/2|-1/2 1/2|]
[ 0| 2/3 -1/3|]
Note that the columns of the printed matrix are the vertices, rays, and lines of the minimal V-representation. Dually, the rows of the following are the inequalities and equations:
sage: Vrep2Hrep(QQ, 2, [(-1/2,0)], [(-1/2,2/3), (1/2,-1/3)], [])
[1 2 3]
[2 4 3]
[-----]
Bases: sage.geometry.polyhedron.double_description_inhomogeneous.PivotedInequalities
Convert H-representation to a minimal V-representation.
INPUT:
EXAMPLES:
sage: from sage.geometry.polyhedron.double_description_inhomogeneous import Hrep2Vrep
sage: Hrep2Vrep(QQ, 2, [(1,2,3), (2,4,3)], [])
[-1/2|-1/2 1/2|]
[ 0| 2/3 -1/3|]
sage: Hrep2Vrep(QQ, 2, [(1,2,3), (2,-2,-3)], [])
[ 1 -1/2|| 1]
[ 0 0||-2/3]
sage: Hrep2Vrep(QQ, 2, [(1,2,3), (2,2,3)], [])
[-1/2| 1/2| 1]
[ 0| 0|-2/3]
sage: Hrep2Vrep(QQ, 2, [(8,7,-2), (1,-4,3), (4,-3,-1)], [])
[ 1 0 -2||]
[ 1 4 -3||]
sage: Hrep2Vrep(QQ, 2, [(1,2,3), (2,4,3), (5,-1,-2)], [])
[-19/5 -1/2| 2/33 1/11|]
[ 22/5 0|-1/33 -2/33|]
sage: Hrep2Vrep(QQ, 2, [(0,2,3), (0,4,3), (0,-1,-2)], [])
[ 0| 1/2 1/3|]
[ 0|-1/3 -1/6|]
sage: Hrep2Vrep(QQ, 2, [], [(1,2,3), (7,8,9)])
[-2||]
[ 1||]
sage: Hrep2Vrep(QQ, 2, [(1,0,0)], []) # universe
[0||1 0]
[0||0 1]
sage: Hrep2Vrep(QQ, 2, [(-1,0,0)], []) # empty
[]
sage: Hrep2Vrep(QQ, 2, [], []) # empty
[]
Compare result to PPL if the base ring is QQ.
This method is for debugging purposes and compares the computation with another backend if available.
INPUT:
EXAMPLES:
sage: from sage.geometry.polyhedron.double_description_inhomogeneous import Hrep2Vrep
sage: H = Hrep2Vrep(QQ, 1, [(1,2)], [])
sage: H.verify([(1,2)], [])
Bases: sage.structure.sage_object.SageObject
Base class for inequalities that may contain linear subspaces
INPUT:
EXAMPLES:
sage: from sage.geometry.polyhedron.double_description_inhomogeneous ....: import PivotedInequalities
sage: piv = PivotedInequalities(QQ, 2)
sage: piv._pivot_inequalities(matrix([(1,1,3), (5,5,7)]))
[1 3]
[5 7]
sage: piv._pivots
(0, 2)
sage: piv._linear_subspace
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1 -1 0]
Bases: sage.geometry.polyhedron.double_description_inhomogeneous.PivotedInequalities
Convert V-representation to a minimal H-representation.
INPUT:
EXAMPLES:
sage: from sage.geometry.polyhedron.double_description_inhomogeneous import Vrep2Hrep
sage: Vrep2Hrep(QQ, 2, [(-1/2,0)], [(-1/2,2/3), (1/2,-1/3)], [])
[1 2 3]
[2 4 3]
[-----]
sage: Vrep2Hrep(QQ, 2, [(1,0), (-1/2,0)], [], [(1,-2/3)])
[ 1/3 2/3 1]
[ 2/3 -2/3 -1]
[--------------]
sage: Vrep2Hrep(QQ, 2, [(-1/2,0)], [(1/2,0)], [(1,-2/3)])
[1 2 3]
[-----]
sage: Vrep2Hrep(QQ, 2, [(1,1), (0,4), (-2,-3)], [], [])
[ 8/13 7/13 -2/13]
[ 1/13 -4/13 3/13]
[ 4/13 -3/13 -1/13]
[-----------------]
sage: Vrep2Hrep(QQ, 2, [(-19/5,22/5), (-1/2,0)], [(2/33,-1/33), (1/11,-2/33)], [])
[10/11 -2/11 -4/11]
[ 66/5 132/5 99/5]
[ 2/11 4/11 6/11]
[-----------------]
sage: Vrep2Hrep(QQ, 2, [(0,0)], [(1/2,-1/3), (1/3,-1/6)], [])
[ 0 -6 -12]
[ 0 12 18]
[-----------]
sage: Vrep2Hrep(QQ, 2, [(-1/2,0)], [], [(1,-2/3)])
[-----]
[1 2 3]
sage: Vrep2Hrep(QQ, 2, [(-1/2,0)], [], [(1,-2/3), (1,0)])
[]
Compare result to PPL if the base ring is QQ.
This method is for debugging purposes and compares the computation with another backend if available.
INPUT:
EXAMPLES:
sage: from sage.geometry.polyhedron.double_description_inhomogeneous import Vrep2Hrep
sage: vertices = [(-1/2,0)]
sage: rays = [(-1/2,2/3), (1/2,-1/3)]
sage: lines = []
sage: V2H = Vrep2Hrep(QQ, 2, vertices, rays, lines)
sage: V2H.verify(vertices, rays, lines)