Double Description for Arbitrary Polyhedra

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 \((1, *, \dots, *)\). The cone over the embedded polyhedron will be called the homogenized cone in the following. Conversely, intersecting the homogenized cone with the hyperplane \(x_0=1\) 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|]

>>> from sage.all import *
>>> from sage.geometry.polyhedron.double_description_inhomogeneous     import Hrep2Vrep, Vrep2Hrep
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(4),Integer(3))], [])
[-1/2|-1/2  1/2|]
[   0| 2/3 -1/3|]

from sage.geometry.polyhedron.double_description_inhomogeneous \
    import Hrep2Vrep, Vrep2Hrep
Hrep2Vrep(QQ, 2, [(1,2,3), (2,4,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]
[-----]

>>> from sage.all import *
>>> Vrep2Hrep(QQ, Integer(2), [(-Integer(1)/Integer(2),Integer(0))], [(-Integer(1)/Integer(2),Integer(2)/Integer(3)), (Integer(1)/Integer(2),-Integer(1)/Integer(3))], [])
[1 2 3]
[2 4 3]
[-----]

Vrep2Hrep(QQ, 2, [(-1/2,0)], [(-1/2,2/3), (1/2,-1/3)], [])
class sage.geometry.polyhedron.double_description_inhomogeneous.Hrep2Vrep(base_ring, dim, inequalities, equations)[source]

Bases: PivotedInequalities

Convert H-representation to a minimal V-representation.

INPUT:

  • base_ring – a field

  • dim – integer; the ambient space dimension

  • inequalities – list of inequalities; each inequality is given as constant term, dim coefficients

  • equations – list of equations; same notation as for inequalities

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, [], [])   # universe
[0||1 0]
[0||0 1]

>>> from sage.all import *
>>> from sage.geometry.polyhedron.double_description_inhomogeneous import Hrep2Vrep
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(4),Integer(3))], [])
[-1/2|-1/2  1/2|]
[   0| 2/3 -1/3|]
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(1),Integer(2),Integer(3)), (Integer(2),-Integer(2),-Integer(3))], [])
[   1 -1/2||   1]
[   0    0||-2/3]
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(2),Integer(3))], [])
[-1/2| 1/2|   1]
[   0|   0|-2/3]
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(8),Integer(7),-Integer(2)), (Integer(1),-Integer(4),Integer(3)), (Integer(4),-Integer(3),-Integer(1))], [])
[ 1  0 -2||]
[ 1  4 -3||]
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(4),Integer(3)), (Integer(5),-Integer(1),-Integer(2))], [])
[-19/5  -1/2| 2/33  1/11|]
[ 22/5     0|-1/33 -2/33|]
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(0),Integer(2),Integer(3)), (Integer(0),Integer(4),Integer(3)), (Integer(0),-Integer(1),-Integer(2))], [])
[   0| 1/2  1/3|]
[   0|-1/3 -1/6|]
>>> Hrep2Vrep(QQ, Integer(2), [], [(Integer(1),Integer(2),Integer(3)), (Integer(7),Integer(8),Integer(9))])
[-2||]
[ 1||]
>>> Hrep2Vrep(QQ, Integer(2), [(Integer(1),Integer(0),Integer(0))], [])    # universe
[0||1 0]
[0||0 1]
>>> Hrep2Vrep(QQ, Integer(2), [(-Integer(1),Integer(0),Integer(0))], [])   # empty
[]
>>> Hrep2Vrep(QQ, Integer(2), [], [])   # universe
[0||1 0]
[0||0 1]

from sage.geometry.polyhedron.double_description_inhomogeneous import Hrep2Vrep
Hrep2Vrep(QQ, 2, [(1,2,3), (2,4,3)], [])
Hrep2Vrep(QQ, 2, [(1,2,3), (2,-2,-3)], [])
Hrep2Vrep(QQ, 2, [(1,2,3), (2,2,3)], [])
Hrep2Vrep(QQ, 2, [(8,7,-2), (1,-4,3), (4,-3,-1)], [])
Hrep2Vrep(QQ, 2, [(1,2,3), (2,4,3), (5,-1,-2)], [])
Hrep2Vrep(QQ, 2, [(0,2,3), (0,4,3), (0,-1,-2)], [])
Hrep2Vrep(QQ, 2, [], [(1,2,3), (7,8,9)])
Hrep2Vrep(QQ, 2, [(1,0,0)], [])    # universe
Hrep2Vrep(QQ, 2, [(-1,0,0)], [])   # empty
Hrep2Vrep(QQ, 2, [], [])   # universe
verify(inequalities, equations)[source]

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

>>> from sage.all import *
>>> from sage.geometry.polyhedron.double_description_inhomogeneous import Hrep2Vrep
>>> H = Hrep2Vrep(QQ, Integer(1), [(Integer(1),Integer(2))], [])
>>> H.verify([(Integer(1),Integer(2))], [])

from sage.geometry.polyhedron.double_description_inhomogeneous import Hrep2Vrep
H = Hrep2Vrep(QQ, 1, [(1,2)], [])
H.verify([(1,2)], [])
class sage.geometry.polyhedron.double_description_inhomogeneous.PivotedInequalities(base_ring, dim)[source]

Bases: SageObject

Base class for inequalities that may contain linear subspaces.

INPUT:

  • base_ring – a field

  • dim – integer; the ambient space dimension

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]

>>> from sage.all import *
>>> from sage.geometry.polyhedron.double_description_inhomogeneous             Ellipsis.:     import PivotedInequalities
>>> piv = PivotedInequalities(QQ, Integer(2))
>>> piv._pivot_inequalities(matrix([(Integer(1),Integer(1),Integer(3)), (Integer(5),Integer(5),Integer(7))]))
[1 3]
[5 7]
>>> piv._pivots
(0, 2)
>>> piv._linear_subspace
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1 -1  0]

from sage.geometry.polyhedron.double_description_inhomogeneous             ....:     import PivotedInequalities
piv = PivotedInequalities(QQ, 2)
piv._pivot_inequalities(matrix([(1,1,3), (5,5,7)]))
piv._pivots
piv._linear_subspace
class sage.geometry.polyhedron.double_description_inhomogeneous.Vrep2Hrep(base_ring, dim, vertices, rays, lines)[source]

Bases: PivotedInequalities

Convert V-representation to a minimal H-representation.

INPUT:

  • base_ring – a field

  • dim – integer; the ambient space dimension

  • vertices – list of vertices; each vertex is given as list of dim coordinates

  • rays – list of rays; each ray is given as list of dim coordinates, not all zero

  • lines – list of line generators; each line is given as list of dim coordinates, not all zero

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

>>> from sage.all import *
>>> from sage.geometry.polyhedron.double_description_inhomogeneous import Vrep2Hrep
>>> Vrep2Hrep(QQ, Integer(2), [(-Integer(1)/Integer(2),Integer(0))], [(-Integer(1)/Integer(2),Integer(2)/Integer(3)), (Integer(1)/Integer(2),-Integer(1)/Integer(3))], [])
[1 2 3]
[2 4 3]
[-----]

>>> Vrep2Hrep(QQ, Integer(2), [(Integer(1),Integer(0)), (-Integer(1)/Integer(2),Integer(0))], [], [(Integer(1),-Integer(2)/Integer(3))])
[ 1/3  2/3    1]
[ 2/3 -2/3   -1]
[--------------]

>>> Vrep2Hrep(QQ, Integer(2), [(-Integer(1)/Integer(2),Integer(0))], [(Integer(1)/Integer(2),Integer(0))], [(Integer(1),-Integer(2)/Integer(3))])
[1 2 3]
[-----]

>>> Vrep2Hrep(QQ, Integer(2), [(Integer(1),Integer(1)), (Integer(0),Integer(4)), (-Integer(2),-Integer(3))], [], [])
[ 8/13  7/13 -2/13]
[ 1/13 -4/13  3/13]
[ 4/13 -3/13 -1/13]
[-----------------]

>>> Vrep2Hrep(QQ, Integer(2), [(-Integer(19)/Integer(5),Integer(22)/Integer(5)), (-Integer(1)/Integer(2),Integer(0))], [(Integer(2)/Integer(33),-Integer(1)/Integer(33)), (Integer(1)/Integer(11),-Integer(2)/Integer(33))], [])
[10/11 -2/11 -4/11]
[ 66/5 132/5  99/5]
[ 2/11  4/11  6/11]
[-----------------]

>>> Vrep2Hrep(QQ, Integer(2), [(Integer(0),Integer(0))], [(Integer(1)/Integer(2),-Integer(1)/Integer(3)), (Integer(1)/Integer(3),-Integer(1)/Integer(6))], [])
[  0  -6 -12]
[  0  12  18]
[-----------]

>>> Vrep2Hrep(QQ, Integer(2), [(-Integer(1)/Integer(2),Integer(0))], [], [(Integer(1),-Integer(2)/Integer(3))])
[-----]
[1 2 3]

>>> Vrep2Hrep(QQ, Integer(2), [(-Integer(1)/Integer(2),Integer(0))], [], [(Integer(1),-Integer(2)/Integer(3)), (Integer(1),Integer(0))])
[]

from sage.geometry.polyhedron.double_description_inhomogeneous import Vrep2Hrep
Vrep2Hrep(QQ, 2, [(-1/2,0)], [(-1/2,2/3), (1/2,-1/3)], [])
Vrep2Hrep(QQ, 2, [(1,0), (-1/2,0)], [], [(1,-2/3)])
Vrep2Hrep(QQ, 2, [(-1/2,0)], [(1/2,0)], [(1,-2/3)])
Vrep2Hrep(QQ, 2, [(1,1), (0,4), (-2,-3)], [], [])
Vrep2Hrep(QQ, 2, [(-19/5,22/5), (-1/2,0)], [(2/33,-1/33), (1/11,-2/33)], [])
Vrep2Hrep(QQ, 2, [(0,0)], [(1/2,-1/3), (1/3,-1/6)], [])
Vrep2Hrep(QQ, 2, [(-1/2,0)], [], [(1,-2/3)])
Vrep2Hrep(QQ, 2, [(-1/2,0)], [], [(1,-2/3), (1,0)])
verify(vertices, rays, lines)[source]

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)

>>> from sage.all import *
>>> from sage.geometry.polyhedron.double_description_inhomogeneous import Vrep2Hrep
>>> vertices = [(-Integer(1)/Integer(2),Integer(0))]
>>> rays = [(-Integer(1)/Integer(2),Integer(2)/Integer(3)), (Integer(1)/Integer(2),-Integer(1)/Integer(3))]
>>> lines = []
>>> V2H = Vrep2Hrep(QQ, Integer(2), vertices, rays, lines)
>>> V2H.verify(vertices, rays, lines)

from sage.geometry.polyhedron.double_description_inhomogeneous import Vrep2Hrep
vertices = [(-1/2,0)]
rays = [(-1/2,2/3), (1/2,-1/3)]
lines = []
V2H = Vrep2Hrep(QQ, 2, vertices, rays, lines)
V2H.verify(vertices, rays, lines)