Base class for polyhedra over \(\ZZ\)¶

class sage.geometry.polyhedron.base_ZZ.Polyhedron_ZZ(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)[source]¶

Bases: Polyhedron_QQ

Base class for Polyhedra over \(\ZZ\).

ehrhart_polynomial(engine=None, variable='t', verbose=False, dual=None, irrational_primal=None, irrational_all_primal=None, maxdet=None, no_decomposition=None, compute_vertex_cones=None, smith_form=None, dualization=None, triangulation=None, triangulation_max_height=None, **kwds)[source]¶

Return the Ehrhart polynomial of this polyhedron.

Let \(P\) be a lattice polytope in \(\RR^d\) and define \(L(P,t) = \# (tP \cap \ZZ^d)\). Then E. Ehrhart proved in 1962 that \(L\) coincides with a rational polynomial of degree \(d\) for integer \(t\). \(L\) is called the Ehrhart polynomial of \(P\). For more information see the Wikipedia article Ehrhart_polynomial.

The Ehrhart polynomial may be computed using either LattE Integrale or Normaliz by setting engine to ‘latte’ or ‘normaliz’ respectively.

INPUT:

engine – string; the backend to use. Allowed values are:
- None (default); When no input is given the Ehrhart polynomial is computed using LattE Integrale (optional)
- 'latte'; use LattE integrale program (optional)
- 'normaliz'; use Normaliz program (optional). The backend of self must be set to ‘normaliz’.
variable – string (default: 't'); the variable in which the Ehrhart polynomial should be expressed
When the engine is ‘latte’ or None, the additional input values are:
- verbose – boolean (default: False); if True, print the whole output of the LattE command.
The following options are passed to the LattE command, for details consult the LattE documentation:
- dual – boolean; triangulate and signed-decompose in the dual space
- irrational_primal – boolean; triangulate in the dual space, signed-decompose in the primal space using irrationalization.
- irrational_all_primal – boolean; triangulate and signed-decompose in the primal space using irrationalization.
- maxdet – integer; decompose down to an index (determinant) of maxdet instead of index 1 (unimodular cones).
- no_decomposition – boolean; do not signed-decompose simplicial cones.
- compute_vertex_cones – string; either ‘cdd’ or ‘lrs’ or ‘4ti2’
- smith_form – string; either ‘ilio’ or ‘lidia’
- dualization – string; either ‘cdd’ or ‘4ti2’
- triangulation – string; ‘cddlib’, ‘4ti2’ or ‘topcom’
- triangulation_max_height – integer; use a uniform distribution of height from 1 to this number

OUTPUT:

The Ehrhart polynomial as a univariate polynomial in variable over a rational field.

See also

latte the interface to LattE Integrale PyNormaliz

EXAMPLES:

To start, we find the Ehrhart polynomial of a three-dimensional simplex, first using engine='latte'. Leaving the engine unspecified sets the engine to ‘latte’ by default:

Sage

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
sage: poly = simplex.ehrhart_polynomial(engine = 'latte')  # optional - latte_int
sage: poly                                                 # optional - latte_int
7/2*t^3 + 2*t^2 - 1/2*t + 1
sage: poly(1)                                              # optional - latte_int
6
sage: len(simplex.integral_points())
6
sage: poly(2)                                              # optional - latte_int
36
sage: len((2*simplex).integral_points())
36

Python

>>> from sage.all import *
>>> simplex = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)),(Integer(3),Integer(3),Integer(3)),(-Integer(3),Integer(2),Integer(1)),(Integer(1),-Integer(1),-Integer(2))])
>>> poly = simplex.ehrhart_polynomial(engine = 'latte')  # optional - latte_int
>>> poly                                                 # optional - latte_int
7/2*t^3 + 2*t^2 - 1/2*t + 1
>>> poly(Integer(1))                                              # optional - latte_int
6
>>> len(simplex.integral_points())
6
>>> poly(Integer(2))                                              # optional - latte_int
36
>>> len((Integer(2)*simplex).integral_points())
36

Sage Live

simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
poly = simplex.ehrhart_polynomial(engine = 'latte')  # optional - latte_int
poly                                                 # optional - latte_int
poly(1)                                              # optional - latte_int
len(simplex.integral_points())
poly(2)                                              # optional - latte_int
len((2*simplex).integral_points())

Now we find the same Ehrhart polynomial, this time using engine='normaliz'. To use the Normaliz engine, the simplex must be defined with backend='normaliz':

Sage

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)], backend='normaliz') # optional - pynormaliz
sage: poly = simplex.ehrhart_polynomial(engine='normaliz') # optional - pynormaliz
sage: poly                                                 # optional - pynormaliz
7/2*t^3 + 2*t^2 - 1/2*t + 1

Python

>>> from sage.all import *
>>> simplex = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)),(Integer(3),Integer(3),Integer(3)),(-Integer(3),Integer(2),Integer(1)),(Integer(1),-Integer(1),-Integer(2))], backend='normaliz') # optional - pynormaliz
>>> poly = simplex.ehrhart_polynomial(engine='normaliz') # optional - pynormaliz
>>> poly                                                 # optional - pynormaliz
7/2*t^3 + 2*t^2 - 1/2*t + 1

Sage Live

simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)], backend='normaliz') # optional - pynormaliz
poly = simplex.ehrhart_polynomial(engine='normaliz') # optional - pynormaliz
poly                                                 # optional - pynormaliz

If the engine='normaliz', the backend should be 'normaliz', otherwise it returns an error:

Sage

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
sage: simplex.ehrhart_polynomial(engine='normaliz')
Traceback (most recent call last):
...
TypeError: The polyhedron's backend should be 'normaliz'

Python

>>> from sage.all import *
>>> simplex = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)),(Integer(3),Integer(3),Integer(3)),(-Integer(3),Integer(2),Integer(1)),(Integer(1),-Integer(1),-Integer(2))])
>>> simplex.ehrhart_polynomial(engine='normaliz')
Traceback (most recent call last):
...
TypeError: The polyhedron's backend should be 'normaliz'

Sage Live

simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
simplex.ehrhart_polynomial(engine='normaliz')

Now we find the Ehrhart polynomials of the unit hypercubes of dimensions three through six. They are computed first with engine='latte' and then with engine='normaliz'. The degree of the Ehrhart polynomial matches the dimension of the hypercube, and the coefficient of the leading monomial equals the volume of the unit hypercube:

Sage

sage: # optional - latte_int
sage: from itertools import product
sage: def hypercube(d):
....:     return Polyhedron(vertices=list(product([0,1],repeat=d)))
sage: hypercube(3).ehrhart_polynomial()
t^3 + 3*t^2 + 3*t + 1
sage: hypercube(4).ehrhart_polynomial()
t^4 + 4*t^3 + 6*t^2 + 4*t + 1
sage: hypercube(5).ehrhart_polynomial()
t^5 + 5*t^4 + 10*t^3 + 10*t^2 + 5*t + 1
sage: hypercube(6).ehrhart_polynomial()
t^6 + 6*t^5 + 15*t^4 + 20*t^3 + 15*t^2 + 6*t + 1

sage: # optional - pynormaliz
sage: from itertools import product
sage: def hypercube(d):
....:     return Polyhedron(vertices=list(product([0,1],repeat=d)),backend='normaliz')
sage: hypercube(3).ehrhart_polynomial(engine='normaliz')
t^3 + 3*t^2 + 3*t + 1
sage: hypercube(4).ehrhart_polynomial(engine='normaliz')
t^4 + 4*t^3 + 6*t^2 + 4*t + 1
sage: hypercube(5).ehrhart_polynomial(engine='normaliz')
t^5 + 5*t^4 + 10*t^3 + 10*t^2 + 5*t + 1
sage: hypercube(6).ehrhart_polynomial(engine='normaliz')
t^6 + 6*t^5 + 15*t^4 + 20*t^3 + 15*t^2 + 6*t + 1

Python

>>> from sage.all import *
>>> # optional - latte_int
>>> from itertools import product
>>> def hypercube(d):
...     return Polyhedron(vertices=list(product([Integer(0),Integer(1)],repeat=d)))
>>> hypercube(Integer(3)).ehrhart_polynomial()
t^3 + 3*t^2 + 3*t + 1
>>> hypercube(Integer(4)).ehrhart_polynomial()
t^4 + 4*t^3 + 6*t^2 + 4*t + 1
>>> hypercube(Integer(5)).ehrhart_polynomial()
t^5 + 5*t^4 + 10*t^3 + 10*t^2 + 5*t + 1
>>> hypercube(Integer(6)).ehrhart_polynomial()
t^6 + 6*t^5 + 15*t^4 + 20*t^3 + 15*t^2 + 6*t + 1

>>> # optional - pynormaliz
>>> from itertools import product
>>> def hypercube(d):
...     return Polyhedron(vertices=list(product([Integer(0),Integer(1)],repeat=d)),backend='normaliz')
>>> hypercube(Integer(3)).ehrhart_polynomial(engine='normaliz')
t^3 + 3*t^2 + 3*t + 1
>>> hypercube(Integer(4)).ehrhart_polynomial(engine='normaliz')
t^4 + 4*t^3 + 6*t^2 + 4*t + 1
>>> hypercube(Integer(5)).ehrhart_polynomial(engine='normaliz')
t^5 + 5*t^4 + 10*t^3 + 10*t^2 + 5*t + 1
>>> hypercube(Integer(6)).ehrhart_polynomial(engine='normaliz')
t^6 + 6*t^5 + 15*t^4 + 20*t^3 + 15*t^2 + 6*t + 1

Sage Live

# optional - latte_int
from itertools import product
def hypercube(d):
    return Polyhedron(vertices=list(product([0,1],repeat=d)))
hypercube(3).ehrhart_polynomial()
hypercube(4).ehrhart_polynomial()
hypercube(5).ehrhart_polynomial()
hypercube(6).ehrhart_polynomial()
# optional - pynormaliz
from itertools import product
def hypercube(d):
    return Polyhedron(vertices=list(product([0,1],repeat=d)),backend='normaliz')
hypercube(3).ehrhart_polynomial(engine='normaliz')
hypercube(4).ehrhart_polynomial(engine='normaliz')
hypercube(5).ehrhart_polynomial(engine='normaliz')
hypercube(6).ehrhart_polynomial(engine='normaliz')

An empty polyhedron:

Sage

sage: p = Polyhedron(ambient_dim=3, vertices=[])
sage: p.ehrhart_polynomial()
0
sage: parent(_)
Univariate Polynomial Ring in t over Rational Field

Python

>>> from sage.all import *
>>> p = Polyhedron(ambient_dim=Integer(3), vertices=[])
>>> p.ehrhart_polynomial()
0
>>> parent(_)
Univariate Polynomial Ring in t over Rational Field

Sage Live

p = Polyhedron(ambient_dim=3, vertices=[])
p.ehrhart_polynomial()
parent(_)

The polyhedron should be compact:

Sage

sage: C = Polyhedron(rays=[[1,2],[2,1]])
sage: C.ehrhart_polynomial()
Traceback (most recent call last):
...
ValueError: Ehrhart polynomial only defined for compact polyhedra

Python

>>> from sage.all import *
>>> C = Polyhedron(rays=[[Integer(1),Integer(2)],[Integer(2),Integer(1)]])
>>> C.ehrhart_polynomial()
Traceback (most recent call last):
...
ValueError: Ehrhart polynomial only defined for compact polyhedra

Sage Live

C = Polyhedron(rays=[[1,2],[2,1]])
C.ehrhart_polynomial()

fibration_generator(dim)[source]¶

Generate the lattice polytope fibrations.

For the purposes of this function, a lattice polytope fiber is a sub-lattice polytope. Projecting the plane spanned by the subpolytope to a point yields another lattice polytope, the base of the fibration.

INPUT:

dim – integer; the dimension of the lattice polytope fiber

OUTPUT:

A generator yielding the distinct lattice polytope fibers of given dimension.

EXAMPLES:

Sage

sage: P = Polyhedron(toric_varieties.P4_11169().fan().rays(), base_ring=ZZ)             # needs palp sage.graphs
sage: list(P.fibration_generator(2))                                        # needs palp sage.graphs
[A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 3 vertices]

Python

>>> from sage.all import *
>>> P = Polyhedron(toric_varieties.P4_11169().fan().rays(), base_ring=ZZ)             # needs palp sage.graphs
>>> list(P.fibration_generator(Integer(2)))                                        # needs palp sage.graphs
[A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 3 vertices]

Sage Live

P = Polyhedron(toric_varieties.P4_11169().fan().rays(), base_ring=ZZ)             # needs palp sage.graphs
list(P.fibration_generator(2))                                        # needs palp sage.graphs

find_translation(translated_polyhedron)[source]¶

Return the translation vector to translated_polyhedron.

INPUT:

translated_polyhedron – a polyhedron

OUTPUT:

A \(\ZZ\)-vector that translates self to translated_polyhedron. A ValueError is raised if translated_polyhedron is not a translation of self, this can be used to check that two polyhedra are not translates of each other.

EXAMPLES:

Sage

sage: X = polytopes.cube()
sage: X.find_translation(X + vector([2,3,5]))
(2, 3, 5)
sage: X.find_translation(2*X)
Traceback (most recent call last):
...
ValueError: polyhedron is not a translation of self

Python

>>> from sage.all import *
>>> X = polytopes.cube()
>>> X.find_translation(X + vector([Integer(2),Integer(3),Integer(5)]))
(2, 3, 5)
>>> X.find_translation(Integer(2)*X)
Traceback (most recent call last):
...
ValueError: polyhedron is not a translation of self

Sage Live

X = polytopes.cube()
X.find_translation(X + vector([2,3,5]))
X.find_translation(2*X)

has_IP_property()[source]¶

Test whether the polyhedron has the IP property.

The IP (interior point) property means that

self is compact (a polytope).
self contains the origin as an interior point.

This implies that

self is full-dimensional.
The dual polyhedron is again a polytope (that is, a compact polyhedron), though not necessarily a lattice polytope.

EXAMPLES:

Sage

sage: Polyhedron([(1,1),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
False
sage: Polyhedron([(0,0),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
False
sage: Polyhedron([(-1,-1),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
True

Python

>>> from sage.all import *
>>> Polyhedron([(Integer(1),Integer(1)),(Integer(1),Integer(0)),(Integer(0),Integer(1))], base_ring=ZZ).has_IP_property()
False
>>> Polyhedron([(Integer(0),Integer(0)),(Integer(1),Integer(0)),(Integer(0),Integer(1))], base_ring=ZZ).has_IP_property()
False
>>> Polyhedron([(-Integer(1),-Integer(1)),(Integer(1),Integer(0)),(Integer(0),Integer(1))], base_ring=ZZ).has_IP_property()
True

Sage Live

Polyhedron([(1,1),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
Polyhedron([(0,0),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
Polyhedron([(-1,-1),(1,0),(0,1)], base_ring=ZZ).has_IP_property()

REFERENCES:

[PALP]

is_lattice_polytope()[source]¶

Return whether the polyhedron is a lattice polytope.

OUTPUT:

True if the polyhedron is compact and has only integral vertices, False otherwise.

EXAMPLES:

Sage

sage: polytopes.cross_polytope(3).is_lattice_polytope()
True
sage: polytopes.regular_polygon(5).is_lattice_polytope()                    # needs sage.rings.number_field
False

Python

>>> from sage.all import *
>>> polytopes.cross_polytope(Integer(3)).is_lattice_polytope()
True
>>> polytopes.regular_polygon(Integer(5)).is_lattice_polytope()                    # needs sage.rings.number_field
False

Sage Live

polytopes.cross_polytope(3).is_lattice_polytope()
polytopes.regular_polygon(5).is_lattice_polytope()                    # needs sage.rings.number_field

is_reflexive()[source]¶

A lattice polytope is reflexive if it contains the origin in its interior and its polar with respect to the origin is a lattice polytope.

Equivalently, it is reflexive if it is of the form \(\{x \in \mathbb{R}^d: Ax \leq 1\}\) for some integer matrix \(A\) and \(d\) the ambient dimension.

EXAMPLES:

Sage

sage: p = Polyhedron(vertices=[(1,0,0),(0,1,0),(0,0,1),(-1,-1,-1)], base_ring=ZZ)
sage: p.is_reflexive()
True
sage: polytopes.hypercube(4).is_reflexive()
True
sage: p = Polyhedron(vertices=[(1,0), (0,2), (-1,0), (0,-1)], base_ring=ZZ)
sage: p.is_reflexive()
False
sage: p = Polyhedron(vertices=[(1,0), (0,2), (-1,0)], base_ring=ZZ)
sage: p.is_reflexive()
False

Python

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1)),(-Integer(1),-Integer(1),-Integer(1))], base_ring=ZZ)
>>> p.is_reflexive()
True
>>> polytopes.hypercube(Integer(4)).is_reflexive()
True
>>> p = Polyhedron(vertices=[(Integer(1),Integer(0)), (Integer(0),Integer(2)), (-Integer(1),Integer(0)), (Integer(0),-Integer(1))], base_ring=ZZ)
>>> p.is_reflexive()
False
>>> p = Polyhedron(vertices=[(Integer(1),Integer(0)), (Integer(0),Integer(2)), (-Integer(1),Integer(0))], base_ring=ZZ)
>>> p.is_reflexive()
False

Sage Live

p = Polyhedron(vertices=[(1,0,0),(0,1,0),(0,0,1),(-1,-1,-1)], base_ring=ZZ)
p.is_reflexive()
polytopes.hypercube(4).is_reflexive()
p = Polyhedron(vertices=[(1,0), (0,2), (-1,0), (0,-1)], base_ring=ZZ)
p.is_reflexive()
p = Polyhedron(vertices=[(1,0), (0,2), (-1,0)], base_ring=ZZ)
p.is_reflexive()

An error is raised, if the polyhedron is not compact:

Sage

sage: p = Polyhedron(rays=[(1,)], base_ring=ZZ)
sage: p.is_reflexive()
Traceback (most recent call last):
...
ValueError: the polyhedron is not compact

Python

>>> from sage.all import *
>>> p = Polyhedron(rays=[(Integer(1),)], base_ring=ZZ)
>>> p.is_reflexive()
Traceback (most recent call last):
...
ValueError: the polyhedron is not compact

Sage Live

p = Polyhedron(rays=[(1,)], base_ring=ZZ)
p.is_reflexive()

minkowski_decompositions()[source]¶

Return all Minkowski sums that add up to the polyhedron.

OUTPUT:

A tuple consisting of pairs \((X,Y)\) of \(\ZZ\)-polyhedra that add up to self. All pairs up to exchange of the summands are returned, that is, \((Y,X)\) is not included if \((X,Y)\) already is.

EXAMPLES:

Sage

sage: square = Polyhedron(vertices=[(0,0),(1,0),(0,1),(1,1)])
sage: square.minkowski_decompositions()
((A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex,
  A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
 (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
  A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices))

Python

>>> from sage.all import *
>>> square = Polyhedron(vertices=[(Integer(0),Integer(0)),(Integer(1),Integer(0)),(Integer(0),Integer(1)),(Integer(1),Integer(1))])
>>> square.minkowski_decompositions()
((A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex,
  A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
 (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
  A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices))

Sage Live

square = Polyhedron(vertices=[(0,0),(1,0),(0,1),(1,1)])
square.minkowski_decompositions()

Example from http://cgi.di.uoa.gr/~amantzaf/geo/

 sage: Q = Polyhedron(vertices=[(4,0), (6,0), (0,3), (4,3)])
 sage: R = Polyhedron(vertices=[(0,0), (5,0), (8,4), (3,2)])
 sage: (Q+R).minkowski_decompositions()
 ((A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 5 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 5 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 6 vertices))

sage: [ len(square.dilation(i).minkowski_decompositions())
....:   for i in range(6) ]
[1, 2, 5, 8, 13, 18]
sage: [ integer_ceil((i^2 + 2*i - 1) / 2) + 1 for i in range(10) ]
[1, 2, 5, 8, 13, 18, 25, 32, 41, 50]

normal_form(algorithm='palp_native', permutation=False)[source]¶

Return the normal form of vertices of the lattice polytope self.

INPUT:

algorithm – must be 'palp_native', the default
permutation – boolean (default: False); if True, the permutation applied to vertices to obtain the normal form is returned as well

For more more detail, see normal_form().

EXAMPLES:

We compute the normal form of the “diamond”:

Sage

sage: d = Polyhedron([(1,0), (0,1), (-1,0), (0,-1)])
sage: d.vertices()
(A vertex at (-1, 0),
 A vertex at (0, -1),
 A vertex at (0, 1),
 A vertex at (1, 0))
sage: d.normal_form()                                                       # needs sage.groups
[(1, 0), (0, 1), (0, -1), (-1, 0)]
sage: d.lattice_polytope().normal_form("palp_native")                       # needs sage.groups
M( 1,  0),
M( 0,  1),
M( 0, -1),
M(-1,  0)
in 2-d lattice M

Python

>>> from sage.all import *
>>> d = Polyhedron([(Integer(1),Integer(0)), (Integer(0),Integer(1)), (-Integer(1),Integer(0)), (Integer(0),-Integer(1))])
>>> d.vertices()
(A vertex at (-1, 0),
 A vertex at (0, -1),
 A vertex at (0, 1),
 A vertex at (1, 0))
>>> d.normal_form()                                                       # needs sage.groups
[(1, 0), (0, 1), (0, -1), (-1, 0)]
>>> d.lattice_polytope().normal_form("palp_native")                       # needs sage.groups
M( 1,  0),
M( 0,  1),
M( 0, -1),
M(-1,  0)
in 2-d lattice M

Sage Live

d = Polyhedron([(1,0), (0,1), (-1,0), (0,-1)])
d.vertices()
d.normal_form()                                                       # needs sage.groups
d.lattice_polytope().normal_form("palp_native")                       # needs sage.groups

Using permutation=True:

Sage

sage: d.normal_form(permutation=True)                                       # needs sage.groups
([(1, 0), (0, 1), (0, -1), (-1, 0)], ())

Python

>>> from sage.all import *
>>> d.normal_form(permutation=True)                                       # needs sage.groups
([(1, 0), (0, 1), (0, -1), (-1, 0)], ())

Sage Live

d.normal_form(permutation=True)                                       # needs sage.groups

It is not possible to compute normal forms for polytopes which do not span the space:

Sage

sage: p = Polyhedron([(1,0,0), (0,1,0), (-1,0,0), (0,-1,0)])
sage: p.normal_form()
Traceback (most recent call last):
...
ValueError: normal form is not defined for lower-dimensional polyhedra, got
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices

Python

>>> from sage.all import *
>>> p = Polyhedron([(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (-Integer(1),Integer(0),Integer(0)), (Integer(0),-Integer(1),Integer(0))])
>>> p.normal_form()
Traceback (most recent call last):
...
ValueError: normal form is not defined for lower-dimensional polyhedra, got
A 2-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices

Sage Live

p = Polyhedron([(1,0,0), (0,1,0), (-1,0,0), (0,-1,0)])
p.normal_form()

The normal form is also not defined for unbounded polyhedra:

Sage

sage: p = Polyhedron(vertices=[[1, 1]], rays=[[1, 0], [0, 1]], base_ring=ZZ)
sage: p.normal_form()
Traceback (most recent call last):
...
ValueError: normal form is not defined for unbounded polyhedra, got
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 rays

Python

>>> from sage.all import *
>>> p = Polyhedron(vertices=[[Integer(1), Integer(1)]], rays=[[Integer(1), Integer(0)], [Integer(0), Integer(1)]], base_ring=ZZ)
>>> p.normal_form()
Traceback (most recent call last):
...
ValueError: normal form is not defined for unbounded polyhedra, got
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex and 2 rays

Sage Live

p = Polyhedron(vertices=[[1, 1]], rays=[[1, 0], [0, 1]], base_ring=ZZ)
p.normal_form()

See Issue #15280 for proposed extensions to these cases.

polar()[source]¶

Return the polar (dual) polytope.

The polytope must have the IP-property (see has_IP_property()), that is, the origin must be an interior point. In particular, it must be full-dimensional.

OUTPUT:

The polytope whose vertices are the coefficient vectors of the inequalities of self with inhomogeneous term normalized to unity.

EXAMPLES:

Sage

sage: p = Polyhedron(vertices=[(1,0,0),(0,1,0),(0,0,1),(-1,-1,-1)], base_ring=ZZ)
sage: p.polar()
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: type(_)
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category.element_class'>
sage: p.polar().base_ring()
Integer Ring

Python

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(1),Integer(0),Integer(0)),(Integer(0),Integer(1),Integer(0)),(Integer(0),Integer(0),Integer(1)),(-Integer(1),-Integer(1),-Integer(1))], base_ring=ZZ)
>>> p.polar()
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
>>> type(_)
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category.element_class'>
>>> p.polar().base_ring()
Integer Ring

Sage Live

p = Polyhedron(vertices=[(1,0,0),(0,1,0),(0,0,1),(-1,-1,-1)], base_ring=ZZ)
p.polar()
type(_)
p.polar().base_ring()