A Longer Introduction to Polyhedral Computations in Sage

Author: Jean-Philippe Labbé <labbe@math.fu-berlin.de>

This tutorial aims to showcase some of the possibilities of Sage concerning polyhedral geometry and combinatorics.

The classic literature on the topic includes:

• Convex Polytopes, Branko Grünbaum, [Gru1967]

• An Introduction to Convex Polytopes, Arne Brøndsted, [Bro1983]

• Lectures on Polytopes, Günter M. Ziegler, [Zie2007]

For the nomenclature, Sage tries to follow:

• Handbook of Discrete and Computational Geometry, Chapter 15, [Goo2004]

Preparation of this document was supported in part by the OpenDreamKit project and written during the SageDays 84 in Olot (Spain).

Lecture 0: Basic definitions and constructions

A real \((k\times d)\)-matrix \(A\) and a real vector \(b\) in \(\mathbb{R}^d\) define a (convex) polyhedron \(P\) as the set of solutions of the system of linear inequalities:

\[A\cdot x + b \geq 0.\]

Each row of \(A\) defines a closed half-space of \(\mathbb{R}^d\). Hence a polyhedron is the intersection of finitely many closed half-spaces in \(\mathbb{R}^d\). The matrix \(A\) may contain equal rows, which may lead to a set of equalities satisfied by the polyhedron. If there are no redundant rows in the above definition, this definition is referred to as the \(\mathbf{H}\) -representation of a polyhedron.

A maximal affine subspace \(L\) contained in a polyhedron is a lineality space of \(P\). Fixing a point \(o\) of the lineality space \(L\) to act as the origin, one can write every point \(p\) inside a polyhedron as a combination

\[p = \ell +\sum_{i=1}^{n}\lambda_iv_i+\sum_{i=1}^{m}\mu_ir_i,\]

where \(\ell\in L\) (using \(o\) as the origin), \(\sum_{i=1}^n\lambda_i=1\), \(\lambda_i\geq0\), \(\mu_i\geq0\), and \(r_i\neq0\) for all \(0\leq i\leq m\) and the set of \(r_i\) ‘s are positively independent (the origin is not in their positive span). For a given point \(p\) there may be many equivalent ways to write the above using different sets \(\{v_i\}_{i=1}^{n}\) and \(\{r_i\}_{i=1}^{m}\). Hence we require the sets to be inclusion minimal sets such that we can get the above property equality for any point \(p\in P\).

The vectors \(v_i\) are called the vertices of \(P\) and the vectors \(r_i\) are called the rays of \(P\). This way to represent a polyhedron is referred to as the \(\mathbf{V}\) -representation of a polyhedron. The first sum represents the convex hull of the vertices \(v_i\) ‘s and the second sum represents a pointed polyhedral cone generated by finitely many rays.

When the lineality space and the rays are reduced to a point (i.e. no rays and no lines) the object is often referred to as a polytope.

Note

As mentioned in the documentation of the constructor when typing Polyhedron?:

You may either define it with vertex/ray/line or inequalities/equations data, but not both. Redundant data will automatically be removed (unless “minimize=False”), and the complementary representation will be computed.

Here is the documentation for the constructor function of Polyhedra.

\(V\)-representation

First, let’s define a polyhedron object as the convex hull of a set of points and some rays.

Sage

sage: P1 = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]])
sage: P1
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

Python

>>> from sage.all import *
>>> P1 = Polyhedron(vertices=[[Integer(1), Integer(0)], [Integer(0), Integer(1)]], rays=[[Integer(1), Integer(1)]])
>>> P1
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

Sage Live

P1 = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]])
P1

The string representation already gives a lot of information:

• the dimension of the polyhedron (the smallest affine space containing it)

• the dimension of the space in which it is defined

• the base ring (\(\mathbb{Z}^2\)) over which the polyhedron lives (this specifies the parent class, see Parents for Polyhedra)

• the number of vertices

• the number of rays

Of course, you want to know what this object looks like:

Sage

sage: P1.plot()
Graphics object consisting of 5 graphics primitives

Python

>>> from sage.all import *
>>> P1.plot()
Graphics object consisting of 5 graphics primitives

Sage Live

P1.plot()

We can also add a lineality space.

Sage

sage: P2 = Polyhedron(vertices=[[1/2, 0, 0], [0, 1/2, 0]],
....:                 rays=[[1, 1, 0]],
....:                 lines=[[0, 0, 1]])
sage: P2
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 2 vertices, 1 ray, 1 line
sage: P2.plot()
Graphics3d Object

Python

>>> from sage.all import *
>>> P2 = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(0), Integer(0)], [Integer(0), Integer(1)/Integer(2), Integer(0)]],
...                 rays=[[Integer(1), Integer(1), Integer(0)]],
...                 lines=[[Integer(0), Integer(0), Integer(1)]])
>>> P2
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 2 vertices, 1 ray, 1 line
>>> P2.plot()
Graphics3d Object

Sage Live

P2 = Polyhedron(vertices=[[1/2, 0, 0], [0, 1/2, 0]],
                rays=[[1, 1, 0]],
                lines=[[0, 0, 1]])
P2
P2.plot()

Notice that the base ring changes because of the value \(\frac{1}{2}\). Indeed, Sage finds an appropriate ring to define the object.

Sage

sage: P1.parent()
Polyhedra in QQ^2
sage: P2.parent()
Polyhedra in QQ^3

Python

>>> from sage.all import *
>>> P1.parent()
Polyhedra in QQ^2
>>> P2.parent()
Polyhedra in QQ^3

Sage Live

P1.parent()
P2.parent()

The chosen ring depends on the input format.

Sage

sage: P3 = Polyhedron(vertices=[[0.5, 0], [0, 0.5]])
sage: P3
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices
sage: P3.parent()
Polyhedra in RDF^2

Python

>>> from sage.all import *
>>> P3 = Polyhedron(vertices=[[RealNumber('0.5'), Integer(0)], [Integer(0), RealNumber('0.5')]])
>>> P3
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices
>>> P3.parent()
Polyhedra in RDF^2

Sage Live

P3 = Polyhedron(vertices=[[0.5, 0], [0, 0.5]])
P3
P3.parent()

Warning

The base ring RDF should be used with care. As it is not an exact ring, certain computations may break or silently produce wrong results, for example when dealing with non-simplicial polyhedra.

The following example demonstrates the limitations of RDF.

Sage

sage: D = polytopes.dodecahedron()                                                  # needs sage.rings.number_field
sage: D                                                                             # needs sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in sqrt5 with defining polynomial x^2 - 5
     with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 20 vertices

sage: vertices_RDF = [n(v.vector(),digits=6) for v in D.vertices()]                 # needs sage.rings.number_field
sage: D_RDF = Polyhedron(vertices=vertices_RDF, base_ring=RDF)                      # needs sage.rings.number_field
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
sage: D_RDF = Polyhedron(vertices=sorted(vertices_RDF), base_ring=RDF)              # needs sage.rings.number_field
Traceback (most recent call last):
...
ValueError: *Error: Numerical inconsistency is found.  Use the GMP exact arithmetic.

Python

>>> from sage.all import *
>>> D = polytopes.dodecahedron()                                                  # needs sage.rings.number_field
>>> D                                                                             # needs sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in sqrt5 with defining polynomial x^2 - 5
     with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 20 vertices

>>> vertices_RDF = [n(v.vector(),digits=Integer(6)) for v in D.vertices()]                 # needs sage.rings.number_field
>>> D_RDF = Polyhedron(vertices=vertices_RDF, base_ring=RDF)                      # needs sage.rings.number_field
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
>>> D_RDF = Polyhedron(vertices=sorted(vertices_RDF), base_ring=RDF)              # needs sage.rings.number_field
Traceback (most recent call last):
...
ValueError: *Error: Numerical inconsistency is found.  Use the GMP exact arithmetic.

Sage Live

D = polytopes.dodecahedron()                                                  # needs sage.rings.number_field
D                                                                             # needs sage.rings.number_field
vertices_RDF = [n(v.vector(),digits=6) for v in D.vertices()]                 # needs sage.rings.number_field
D_RDF = Polyhedron(vertices=vertices_RDF, base_ring=RDF)                      # needs sage.rings.number_field
D_RDF = Polyhedron(vertices=sorted(vertices_RDF), base_ring=RDF)              # needs sage.rings.number_field

If the input of the polyhedron consists of python float, it automatically converts the data to RDF:

Sage

sage: Polyhedron(vertices=[[float(1.1)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex

Python

>>> from sage.all import *
>>> Polyhedron(vertices=[[float(RealNumber('1.1'))]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex

Sage Live

Polyhedron(vertices=[[float(1.1)]])

It is also possible to define a polyhedron over algebraic numbers.

Sage

sage: # needs sage.rings.number_field
sage: sqrt_2 = AA(2)^(1/2)
sage: cbrt_2 = AA(2)^(1/3)
sage: timeit('Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]])')     # random
5 loops, best of 3: 43.2 ms per loop
sage: P4 = Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]]); P4
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> sqrt_2 = AA(Integer(2))**(Integer(1)/Integer(2))
>>> cbrt_2 = AA(Integer(2))**(Integer(1)/Integer(3))
>>> timeit('Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]])')     # random
5 loops, best of 3: 43.2 ms per loop
>>> P4 = Polyhedron(vertices=[[sqrt_2, Integer(0)], [Integer(0), cbrt_2]]); P4
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

Sage Live

# needs sage.rings.number_field
sqrt_2 = AA(2)^(1/2)
cbrt_2 = AA(2)^(1/3)
timeit('Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]])')     # random
P4 = Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]]); P4

There is another way to create a polyhedron over algebraic numbers:

Sage

sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^2 - 2, embedding=AA(2)**(1/2))
sage: L.<b> = NumberField(x^3 - 2, embedding=AA(2)**(1/3))
sage: timeit('Polyhedron(vertices=[[a, 0], [0, b]])')               # random
5 loops, best of 3: 39.9 ms per loop
sage: P5 = Polyhedron(vertices=[[a, 0], [0, b]]); P5
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> K = NumberField(x**Integer(2) - Integer(2), embedding=AA(Integer(2))**(Integer(1)/Integer(2)), names=('a',)); (a,) = K._first_ngens(1)
>>> L = NumberField(x**Integer(3) - Integer(2), embedding=AA(Integer(2))**(Integer(1)/Integer(3)), names=('b',)); (b,) = L._first_ngens(1)
>>> timeit('Polyhedron(vertices=[[a, 0], [0, b]])')               # random
5 loops, best of 3: 39.9 ms per loop
>>> P5 = Polyhedron(vertices=[[a, Integer(0)], [Integer(0), b]]); P5
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices

Sage Live

# needs sage.rings.number_field
K.<a> = NumberField(x^2 - 2, embedding=AA(2)**(1/2))
L.<b> = NumberField(x^3 - 2, embedding=AA(2)**(1/3))
timeit('Polyhedron(vertices=[[a, 0], [0, b]])')               # random
P5 = Polyhedron(vertices=[[a, 0], [0, b]]); P5

If the base ring is known it may be a good option to use the proper sage.rings.number_field.number_field.number_field.composite_fields():

Sage

sage: # needs sage.rings.number_field
sage: J = K.composite_fields(L)[0]
sage: timeit('Polyhedron(vertices=[[J(a), 0], [0, J(b)]])')         # random
25 loops, best of 3: 9.8 ms per loop
sage: P5_comp = Polyhedron(vertices=[[J(a), 0], [0, J(b)]]); P5_comp
A 1-dimensional polyhedron
 in (Number Field in ab with defining polynomial
     x^6 - 6*x^4 - 4*x^3 + 12*x^2 - 24*x - 4
     with ab = -0.1542925124782219?)^2
 defined as the convex hull of 2 vertices

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> J = K.composite_fields(L)[Integer(0)]
>>> timeit('Polyhedron(vertices=[[J(a), 0], [0, J(b)]])')         # random
25 loops, best of 3: 9.8 ms per loop
>>> P5_comp = Polyhedron(vertices=[[J(a), Integer(0)], [Integer(0), J(b)]]); P5_comp
A 1-dimensional polyhedron
 in (Number Field in ab with defining polynomial
     x^6 - 6*x^4 - 4*x^3 + 12*x^2 - 24*x - 4
     with ab = -0.1542925124782219?)^2
 defined as the convex hull of 2 vertices

Sage Live

# needs sage.rings.number_field
J = K.composite_fields(L)[0]
timeit('Polyhedron(vertices=[[J(a), 0], [0, J(b)]])')         # random
P5_comp = Polyhedron(vertices=[[J(a), 0], [0, J(b)]]); P5_comp

Polyhedral computations with the Symbolic Ring are not implemented. It is not possible to define a polyhedron over it:

Sage

sage: sqrt_2s = sqrt(2)                                                             # needs sage.symbolic
sage: cbrt_2s = 2^(1/3)                                                             # needs sage.symbolic
sage: Polyhedron(vertices=[[sqrt_2s, 0], [0, cbrt_2s]])                             # needs sage.symbolic
Traceback (most recent call last):
...
ValueError: no default backend for computations with Symbolic Ring

Python

>>> from sage.all import *
>>> sqrt_2s = sqrt(Integer(2))                                                             # needs sage.symbolic
>>> cbrt_2s = Integer(2)**(Integer(1)/Integer(3))                                                             # needs sage.symbolic
>>> Polyhedron(vertices=[[sqrt_2s, Integer(0)], [Integer(0), cbrt_2s]])                             # needs sage.symbolic
Traceback (most recent call last):
...
ValueError: no default backend for computations with Symbolic Ring

Sage Live

sqrt_2s = sqrt(2)                                                             # needs sage.symbolic
cbrt_2s = 2^(1/3)                                                             # needs sage.symbolic
Polyhedron(vertices=[[sqrt_2s, 0], [0, cbrt_2s]])                             # needs sage.symbolic

Similarly, it is not possible to create polyhedron objects over RR (no matter how many bits of precision).

Sage

sage: F45 = RealField(45)
sage: F100 = RealField(100)
sage: f = 1.1
sage: Polyhedron(vertices=[[F45(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'
sage: Polyhedron(vertices=[[F100(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'

Python

>>> from sage.all import *
>>> F45 = RealField(Integer(45))
>>> F100 = RealField(Integer(100))
>>> f = RealNumber('1.1')
>>> Polyhedron(vertices=[[F45(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'
>>> Polyhedron(vertices=[[F100(f)]])
Traceback (most recent call last):
...
ValueError: the only allowed inexact ring is 'RDF' with backend 'cdd'

Sage Live

F45 = RealField(45)
F100 = RealField(100)
f = 1.1
Polyhedron(vertices=[[F45(f)]])
Polyhedron(vertices=[[F100(f)]])

There is one exception, when the number of bits of precision is 53, then the base ring is converted to RDF:

Sage

sage: F53 = RealField(53)
sage: Polyhedron(vertices=[[F53(f)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex
sage: type(Polyhedron(vertices=[[F53(f)]]))
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>

Python

>>> from sage.all import *
>>> F53 = RealField(Integer(53))
>>> Polyhedron(vertices=[[F53(f)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex
>>> type(Polyhedron(vertices=[[F53(f)]]))
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>

Sage Live

F53 = RealField(53)
Polyhedron(vertices=[[F53(f)]])
type(Polyhedron(vertices=[[F53(f)]]))

This behavior can be seen as wrong, but it allows the following to be acceptable by Sage:

Sage

sage: Polyhedron([(1.0, 2.3), (3.5, 2.0)])
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices

Python

>>> from sage.all import *
>>> Polyhedron([(RealNumber('1.0'), RealNumber('2.3')), (RealNumber('3.5'), RealNumber('2.0'))])
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices

Sage Live

Polyhedron([(1.0, 2.3), (3.5, 2.0)])

without having specified the base ring RDF by the user.

\(H\)-representation

If a polyhedron object was constructed via a \(V\)-representation, Sage can provide the \(H\)-representation of the object.

Sage

sage: for h in P1.Hrepresentation():
....:     print(h)
An inequality (1, 1) x - 1 >= 0
An inequality (1, -1) x + 1 >= 0
An inequality (-1, 1) x + 1 >= 0

Python

>>> from sage.all import *
>>> for h in P1.Hrepresentation():
...     print(h)
An inequality (1, 1) x - 1 >= 0
An inequality (1, -1) x + 1 >= 0
An inequality (-1, 1) x + 1 >= 0

Sage Live

for h in P1.Hrepresentation():
    print(h)

Each line gives a row of the matrix \(A\) and an entry of the vector \(b\). The variable \(x\) is a vector in the ambient space where P1 is defined. The \(H\)-representation may contain equations:

Sage

sage: P3.Hrepresentation()
(An inequality (-2.0, 0.0) x + 1.0 >= 0,
 An inequality (1.0, 0.0) x + 0.0 >= 0,
 An equation (1.0, 1.0) x - 0.5 == 0)

Python

>>> from sage.all import *
>>> P3.Hrepresentation()
(An inequality (-2.0, 0.0) x + 1.0 >= 0,
 An inequality (1.0, 0.0) x + 0.0 >= 0,
 An equation (1.0, 1.0) x - 0.5 == 0)

Sage Live

P3.Hrepresentation()

The construction of a polyhedron object via its \(H\)-representation, requires a precise format. Each inequality \((a_{i1}, \dots, a_{id})\cdot x + b_i \geq 0\) must be written as [b_i,a_i1, ..., a_id].

Sage

sage: P3_H = Polyhedron(ieqs = [[1.0, -2, 0], [0, 1, 0]], eqns = [[-0.5, 1, 1]])
sage: P3 == P3_H
True
sage: P3_H.Vrepresentation()
(A vertex at (0.0, 0.5), A vertex at (0.5, 0.0))

Python

>>> from sage.all import *
>>> P3_H = Polyhedron(ieqs = [[RealNumber('1.0'), -Integer(2), Integer(0)], [Integer(0), Integer(1), Integer(0)]], eqns = [[-RealNumber('0.5'), Integer(1), Integer(1)]])
>>> P3 == P3_H
True
>>> P3_H.Vrepresentation()
(A vertex at (0.0, 0.5), A vertex at (0.5, 0.0))

Sage Live

P3_H = Polyhedron(ieqs = [[1.0, -2, 0], [0, 1, 0]], eqns = [[-0.5, 1, 1]])
P3 == P3_H
P3_H.Vrepresentation()

It is worth using the parameter eqns to shorten the construction of the object. In the following example, the first four rows are the negative of the second group of four rows.

Sage

sage: H = [[0, 0, 0, 0, 0, 0, 0, 0, 1],
....:  [0, 0, 0, 0, 0, 0, 1, 0, 0],
....:  [-2, 1, 1, 1, 1, 1, 0, 0, 0],
....:  [0, 0, 0, 0, 0, 0, 0, 1, 0],
....:  [0, 0, 0, 0, 0, 0, 0, 0, -1],
....:  [0, 0, 0, 0, 0, 0, -1, 0, 0],
....:  [2, -1, -1, -1, -1, -1, 0, 0, 0],
....:  [0, 0, 0, 0, 0, 0, 0, -1, 0],
....:  [2, -1, -1, -1, -1, 0, 0, 0, 0],
....:  [0, 0, 0, 0, 1, 0, 0, 0, 0],
....:  [0, 0, 0, 1, 0, 0, 0, 0, 0],
....:  [0, 0, 1, 0, 0, 0, 0, 0, 0],
....:  [-1, 1, 1, 1, 1, 0, 0, 0, 0],
....:  [1, 0, 0, -1, 0, 0, 0, 0, 0],
....:  [0, 1, 0, 0, 0, 0, 0, 0, 0],
....:  [1, 0, 0, 0, -1, 0, 0, 0, 0],
....:  [1, 0, -1, 0, 0, 0, 0, 0, 0],
....:  [1, -1, 0, 0, 0, 0, 0, 0, 0]]
sage: timeit('Polyhedron(ieqs = H)')  # random
125 loops, best of 3: 5.99 ms per loop
sage: timeit('Polyhedron(ieqs = H[8:], eqns = H[:4])')  # random
125 loops, best of 3: 4.78 ms per loop
sage: Polyhedron(ieqs = H) == Polyhedron(ieqs = H[8:], eqns = H[:4])
True

Python

>>> from sage.all import *
>>> H = [[Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1)],
...  [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0)],
...  [-Integer(2), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)],
...  [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)],
...  [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1)],
...  [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(0)],
...  [Integer(2), -Integer(1), -Integer(1), -Integer(1), -Integer(1), -Integer(1), Integer(0), Integer(0), Integer(0)],
...  [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0)],
...  [Integer(2), -Integer(1), -Integer(1), -Integer(1), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [-Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(1), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(1), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(1), Integer(0), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],
...  [Integer(1), -Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)]]
>>> timeit('Polyhedron(ieqs = H)')  # random
125 loops, best of 3: 5.99 ms per loop
>>> timeit('Polyhedron(ieqs = H[8:], eqns = H[:4])')  # random
125 loops, best of 3: 4.78 ms per loop
>>> Polyhedron(ieqs = H) == Polyhedron(ieqs = H[Integer(8):], eqns = H[:Integer(4)])
True

Sage Live

H = [[0, 0, 0, 0, 0, 0, 0, 0, 1],
 [0, 0, 0, 0, 0, 0, 1, 0, 0],
 [-2, 1, 1, 1, 1, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, -1],
 [0, 0, 0, 0, 0, 0, -1, 0, 0],
 [2, -1, -1, -1, -1, -1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, -1, 0],
 [2, -1, -1, -1, -1, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0, 0, 0],
 [-1, 1, 1, 1, 1, 0, 0, 0, 0],
 [1, 0, 0, -1, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 0, 0, -1, 0, 0, 0, 0],
 [1, 0, -1, 0, 0, 0, 0, 0, 0],
 [1, -1, 0, 0, 0, 0, 0, 0, 0]]
timeit('Polyhedron(ieqs = H)')  # random
timeit('Polyhedron(ieqs = H[8:], eqns = H[:4])')  # random
Polyhedron(ieqs = H) == Polyhedron(ieqs = H[8:], eqns = H[:4])

Of course, this is a toy example, but it is generally worth to preprocess the data before defining the polyhedron if possible.

Lecture 1: Representation objects

Many objects are related to the \(H\)- and \(V\)-representations. Sage has classes implemented for them.

\(H\)-representation

You can store the \(H\)-representation in a variable and use the inequalities and equalities as objects.

Sage

sage: P3_QQ = Polyhedron(vertices=[[0.5, 0], [0, 0.5]], base_ring=QQ)
sage: HRep = P3_QQ.Hrepresentation()
sage: H1 = HRep[0]; H1
An equation (2, 2) x - 1 == 0
sage: H2 = HRep[1]; H2
An inequality (0, -2) x + 1 >= 0
sage: H1.<tab>   # not tested
sage: H1.A()
(2, 2)
sage: H1.b()
-1
sage: H1.is_equation()
True
sage: H1.is_inequality()
False
sage: H1.contains(vector([0,0]))
False
sage: H2.contains(vector([0,0]))
True
sage: H1.is_incident(H2)
True

Python

>>> from sage.all import *
>>> P3_QQ = Polyhedron(vertices=[[RealNumber('0.5'), Integer(0)], [Integer(0), RealNumber('0.5')]], base_ring=QQ)
>>> HRep = P3_QQ.Hrepresentation()
>>> H1 = HRep[Integer(0)]; H1
An equation (2, 2) x - 1 == 0
>>> H2 = HRep[Integer(1)]; H2
An inequality (0, -2) x + 1 >= 0
>>> H1.<tab>   # not tested
>>> H1.A()
(2, 2)
>>> H1.b()
-1
>>> H1.is_equation()
True
>>> H1.is_inequality()
False
>>> H1.contains(vector([Integer(0),Integer(0)]))
False
>>> H2.contains(vector([Integer(0),Integer(0)]))
True
>>> H1.is_incident(H2)
True

Sage Live

P3_QQ = Polyhedron(vertices=[[0.5, 0], [0, 0.5]], base_ring=QQ)
HRep = P3_QQ.Hrepresentation()
H1 = HRep[0]; H1
H2 = HRep[1]; H2
H1.<tab>   # not tested
H1.A()
H1.b()
H1.is_equation()
H1.is_inequality()
H1.contains(vector([0,0]))
H2.contains(vector([0,0]))
H1.is_incident(H2)

It is possible to obtain the different objects of the \(H\)-representation as follows.

Sage

sage: P3_QQ.equations()
(An equation (2, 2) x - 1 == 0,)
sage: P3_QQ.inequalities()
(An inequality (0, -2) x + 1 >= 0, An inequality (0, 1) x + 0 >= 0)

Python

>>> from sage.all import *
>>> P3_QQ.equations()
(An equation (2, 2) x - 1 == 0,)
>>> P3_QQ.inequalities()
(An inequality (0, -2) x + 1 >= 0, An inequality (0, 1) x + 0 >= 0)

Sage Live

P3_QQ.equations()
P3_QQ.inequalities()

Note

It is recommended to use equations or equation_generator (and similarly for inequalities) if one wants to iterate over them instead of equations_list.

\(V\)-representation

Similarly, you can access vertices, rays and lines of the polyhedron.

Sage

sage: VRep = P2.Vrepresentation(); VRep
(A line in the direction (0, 0, 1),
 A vertex at (0, 1/2, 0),
 A vertex at (1/2, 0, 0),
 A ray in the direction (1, 1, 0))
sage: L = VRep[0]; L
A line in the direction (0, 0, 1)
sage: V = VRep[1]; V
A vertex at (0, 1/2, 0)
sage: R = VRep[3]; R
A ray in the direction (1, 1, 0)
sage: L.is_line()
True
sage: L.is_incident(V)
True
sage: R.is_incident(L)
False
sage: L.vector()
(0, 0, 1)
sage: V.vector()
(0, 1/2, 0)

Python

>>> from sage.all import *
>>> VRep = P2.Vrepresentation(); VRep
(A line in the direction (0, 0, 1),
 A vertex at (0, 1/2, 0),
 A vertex at (1/2, 0, 0),
 A ray in the direction (1, 1, 0))
>>> L = VRep[Integer(0)]; L
A line in the direction (0, 0, 1)
>>> V = VRep[Integer(1)]; V
A vertex at (0, 1/2, 0)
>>> R = VRep[Integer(3)]; R
A ray in the direction (1, 1, 0)
>>> L.is_line()
True
>>> L.is_incident(V)
True
>>> R.is_incident(L)
False
>>> L.vector()
(0, 0, 1)
>>> V.vector()
(0, 1/2, 0)

Sage Live

VRep = P2.Vrepresentation(); VRep
L = VRep[0]; L
V = VRep[1]; V
R = VRep[3]; R
L.is_line()
L.is_incident(V)
R.is_incident(L)
L.vector()
V.vector()

It is possible to obtain the different objects of the \(V\)-representation as follows.

Sage

sage: P2.vertices()
(A vertex at (0, 1/2, 0), A vertex at (1/2, 0, 0))
sage: P2.rays()
(A ray in the direction (1, 1, 0),)
sage: P2.lines()
(A line in the direction (0, 0, 1),)

sage: P2.vertices_matrix()
[  0 1/2]
[1/2   0]
[  0   0]

Python

>>> from sage.all import *
>>> P2.vertices()
(A vertex at (0, 1/2, 0), A vertex at (1/2, 0, 0))
>>> P2.rays()
(A ray in the direction (1, 1, 0),)
>>> P2.lines()
(A line in the direction (0, 0, 1),)

>>> P2.vertices_matrix()
[  0 1/2]
[1/2   0]
[  0   0]

Sage Live

P2.vertices()
P2.rays()
P2.lines()
P2.vertices_matrix()

Note

It is recommended to use vertices or vertex_generator (and similarly for rays and lines) if one wants to iterate over them instead of vertices_list.

Lecture 2: Backends for polyhedral computations

To deal with polyhedron objects, Sage currently has four backends available. These backends offer various functionalities and have their own specific strengths and limitations.

• The cdd backend for polyhedral computations

  • The cdd and cddplus homepage

• The PPL (Parma Polyhedra Library) backend for polyhedral computations

  • The Parma Polyhedra Library homepage

• The polymake backend for polyhedral computations

  • The polymake project for convex geometry

• The Python backend

  • This is a python backend that provides an implementation of polyhedron over irrational coordinates.

• The Normaliz backend for polyhedral computations, (requires the optional package pynormaliz)

  • Normaliz Homepage

The default backend is ppl. Whenever one needs speed it is good to try out the different backends. The backend field is not specifically designed for dealing with extremal computations but can do computations in exact coordinates.

The cdd backend

In order to use a specific backend, we specify the backend parameter.

Sage

sage: P1_cdd = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]], backend='cdd')
sage: P1_cdd
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

Python

>>> from sage.all import *
>>> P1_cdd = Polyhedron(vertices=[[Integer(1), Integer(0)], [Integer(0), Integer(1)]], rays=[[Integer(1), Integer(1)]], backend='cdd')
>>> P1_cdd
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

Sage Live

P1_cdd = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]], backend='cdd')
P1_cdd

A priori, it seems that nothing changed, but …

Sage

sage: P1_cdd.parent()
Polyhedra in QQ^2

Python

>>> from sage.all import *
>>> P1_cdd.parent()
Polyhedra in QQ^2

Sage Live

P1_cdd.parent()

The polyhedron P1_cdd is now considered as a rational polyhedron by the backend cdd. We can also check the backend and the parent using type:

Sage

sage: type(P1_cdd)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_cdd_with_category.element_class'>
sage: type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>

Python

>>> from sage.all import *
>>> type(P1_cdd)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_cdd_with_category.element_class'>
>>> type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>

Sage Live

type(P1_cdd)
type(P1)

We see

• the backend used (ex: backend_cdd)

• followed by a dot ‘.’

• the parent (ex: Polyhedra_QQ) followed again by the backend,

and you can safely ignore the rest for the purpose of this tutorial.

The cdd backend accepts also entries in RDF:

Sage

sage: P3_cdd = Polyhedron(vertices=[[0.5, 0], [0, 0.5]], backend='cdd')
sage: P3_cdd
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices

Python

>>> from sage.all import *
>>> P3_cdd = Polyhedron(vertices=[[RealNumber('0.5'), Integer(0)], [Integer(0), RealNumber('0.5')]], backend='cdd')
>>> P3_cdd
A 1-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices

Sage Live

P3_cdd = Polyhedron(vertices=[[0.5, 0], [0, 0.5]], backend='cdd')
P3_cdd

but not algebraic or symbolic values:

Sage

sage: P4_cdd = Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]], backend='cdd')       # needs sage.rings.number_field
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Algebraic Real Field).

sage: P5_cdd = Polyhedron(vertices=[[sqrt_2s, 0], [0, cbrt_2s]], backend='cdd')     # needs sage.symbolic
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Symbolic Ring).

Python

>>> from sage.all import *
>>> P4_cdd = Polyhedron(vertices=[[sqrt_2, Integer(0)], [Integer(0), cbrt_2]], backend='cdd')       # needs sage.rings.number_field
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Algebraic Real Field).

>>> P5_cdd = Polyhedron(vertices=[[sqrt_2s, Integer(0)], [Integer(0), cbrt_2s]], backend='cdd')     # needs sage.symbolic
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Symbolic Ring).

Sage Live

P4_cdd = Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]], backend='cdd')       # needs sage.rings.number_field
P5_cdd = Polyhedron(vertices=[[sqrt_2s, 0], [0, cbrt_2s]], backend='cdd')     # needs sage.symbolic

It is possible to get the cdd format of any polyhedron object defined over \(\mathbb{Z}\), \(\mathbb{Q}\), or RDF:

Sage

sage: print(P1.cdd_Vrepresentation())
V-representation
begin
 3 3 rational
 0 1 1
 1 0 1
 1 1 0
end
sage: print(P3.cdd_Hrepresentation())
H-representation
linearity 1 1
begin
 3 3 real
 -0.5 1.0 1.0
 1.0 -2.0 0.0
 0.0 1.0 0.0
end

Python

>>> from sage.all import *
>>> print(P1.cdd_Vrepresentation())
V-representation
begin
 3 3 rational
 0 1 1
 1 0 1
 1 1 0
end
>>> print(P3.cdd_Hrepresentation())
H-representation
linearity 1 1
begin
 3 3 real
 -0.5 1.0 1.0
 1.0 -2.0 0.0
 0.0 1.0 0.0
end

Sage Live

print(P1.cdd_Vrepresentation())
print(P3.cdd_Hrepresentation())

You can also write this data to a file using the method .write_cdd_Hrepresentation(filename) or .write_cdd_Vrepresentation(filename), where filename is a string containing a path to a file to be written.

The ppl backend

The default backend for polyhedron objects is ppl.

Sage

sage: type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
sage: type(P2)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
sage: type(P3)  # has entries like 0.5
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>

Python

>>> from sage.all import *
>>> type(P1)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
>>> type(P2)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_ppl_with_category.element_class'>
>>> type(P3)  # has entries like 0.5
<class 'sage.geometry.polyhedron.parent.Polyhedra_RDF_cdd_with_category.element_class'>

Sage Live

type(P1)
type(P2)
type(P3)  # has entries like 0.5

As you see, it does not accepts values in RDF and the polyhedron constructor used the cdd backend.

The polymake backend

The polymake backend is provided when the experimental package polymake for sage is installed.

Sage

sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)],             # optional - jupymake
....:                rays=[(1,1)], lines=[],
....:                backend='polymake', base_ring=QQ)

Python

>>> from sage.all import *
>>> p = Polyhedron(vertices=[(Integer(0),Integer(0)),(Integer(1),Integer(0)),(Integer(0),Integer(1))],             # optional - jupymake
...                rays=[(Integer(1),Integer(1))], lines=[],
...                backend='polymake', base_ring=QQ)

Sage Live

p = Polyhedron(vertices=[(0,0),(1,0),(0,1)],             # optional - jupymake
               rays=[(1,1)], lines=[],
               backend='polymake', base_ring=QQ)

An example with quadratic field:

Sage

sage: V = polytopes.dodecahedron().vertices_list()                                  # needs sage.rings.number_field
sage: Polyhedron(vertices=V, backend='polymake')    # optional - jupymake           # needs sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 20 vertices

Python

>>> from sage.all import *
>>> V = polytopes.dodecahedron().vertices_list()                                  # needs sage.rings.number_field
>>> Polyhedron(vertices=V, backend='polymake')    # optional - jupymake           # needs sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 20 vertices

Sage Live

V = polytopes.dodecahedron().vertices_list()                                  # needs sage.rings.number_field
Polyhedron(vertices=V, backend='polymake')    # optional - jupymake           # needs sage.rings.number_field

The field backend

As it turns out, the rational numbers do not suffice to represent all combinatorial types of polytopes. For example, Perles constructed a \(8\)-dimensional polytope with \(12\) vertices which does not have a realization with rational coordinates, see Example 6.21 p. 172 of [Zie2007]. Furthermore, if one wants a realization to have specific geometric property, such as symmetry, one also sometimes need irrational coordinates.

The backend field provides the necessary tools to deal with such examples.

Sage

sage: type(D)                                                                       # needs sage.rings.number_field
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>

Python

>>> from sage.all import *
>>> type(D)                                                                       # needs sage.rings.number_field
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>

Sage Live

type(D)                                                                       # needs sage.rings.number_field

Any time that the coordinates should be in an extension of the rationals, the backend field is called.

Sage

sage: # needs sage.rings.number_field
sage: P4.parent()
Polyhedra in AA^2
sage: P5.parent()
Polyhedra in AA^2
sage: type(P4)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
sage: type(P5)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>

Python

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P4.parent()
Polyhedra in AA^2
>>> P5.parent()
Polyhedra in AA^2
>>> type(P4)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
>>> type(P5)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>

Sage Live

# needs sage.rings.number_field
P4.parent()
P5.parent()
type(P4)
type(P5)

The normaliz backend

The fourth backend is normaliz and is an optional Sage package.

Sage

sage: # optional - pynormaliz
sage: P1_normaliz = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]],
....:                          backend='normaliz')
sage: type(P1_normaliz)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>
sage: P2_normaliz = Polyhedron(vertices=[[1/2, 0, 0], [0, 1/2, 0]],
....:                          rays=[[1, 1, 0]],
....:                          lines=[[0, 0, 1]], backend='normaliz')
sage: type(P2_normaliz)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>

Python

>>> from sage.all import *
>>> # optional - pynormaliz
>>> P1_normaliz = Polyhedron(vertices=[[Integer(1), Integer(0)], [Integer(0), Integer(1)]], rays=[[Integer(1), Integer(1)]],
...                          backend='normaliz')
>>> type(P1_normaliz)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>
>>> P2_normaliz = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(0), Integer(0)], [Integer(0), Integer(1)/Integer(2), Integer(0)]],
...                          rays=[[Integer(1), Integer(1), Integer(0)]],
...                          lines=[[Integer(0), Integer(0), Integer(1)]], backend='normaliz')
>>> type(P2_normaliz)
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>

Sage Live

# optional - pynormaliz
P1_normaliz = Polyhedron(vertices=[[1, 0], [0, 1]], rays=[[1, 1]],
                         backend='normaliz')
type(P1_normaliz)
P2_normaliz = Polyhedron(vertices=[[1/2, 0, 0], [0, 1/2, 0]],
                         rays=[[1, 1, 0]],
                         lines=[[0, 0, 1]], backend='normaliz')
type(P2_normaliz)

This backend does not work with RDF or other inexact fields.

Sage

sage: P3_normaliz = Polyhedron(vertices=[[0.5, 0], [0, 0.5]], backend='normaliz')   # optional - pynormaliz
Traceback (most recent call last):
...
ValueError: No such backend (=normaliz) implemented for given basering (=Real Double Field).

Python

>>> from sage.all import *
>>> P3_normaliz = Polyhedron(vertices=[[RealNumber('0.5'), Integer(0)], [Integer(0), RealNumber('0.5')]], backend='normaliz')   # optional - pynormaliz
Traceback (most recent call last):
...
ValueError: No such backend (=normaliz) implemented for given basering (=Real Double Field).

Sage Live

P3_normaliz = Polyhedron(vertices=[[0.5, 0], [0, 0.5]], backend='normaliz')   # optional - pynormaliz

The normaliz backend provides fast computations with algebraic numbers. They can be entered as elements of an embedded number field, the field of algebraic numbers, or even the symbolic ring. Internally the computation is done using an embedded number field.

Sage

sage: # optional - pynormaliz
sage: P4_normaliz = Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]],
....:                          backend='normaliz')
sage: P4_normaliz
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices
sage: P5_normaliz = Polyhedron(vertices=[[sqrt_2s, 0], [0, cbrt_2s]],
....:                          backend='normaliz')
sage: P5_normaliz
A 1-dimensional polyhedron in (Symbolic Ring)^2 defined as the convex hull of 2 vertices

Python

>>> from sage.all import *
>>> # optional - pynormaliz
>>> P4_normaliz = Polyhedron(vertices=[[sqrt_2, Integer(0)], [Integer(0), cbrt_2]],
...                          backend='normaliz')
>>> P4_normaliz
A 1-dimensional polyhedron in AA^2 defined as the convex hull of 2 vertices
>>> P5_normaliz = Polyhedron(vertices=[[sqrt_2s, Integer(0)], [Integer(0), cbrt_2s]],
...                          backend='normaliz')
>>> P5_normaliz
A 1-dimensional polyhedron in (Symbolic Ring)^2 defined as the convex hull of 2 vertices

Sage Live

# optional - pynormaliz
P4_normaliz = Polyhedron(vertices=[[sqrt_2, 0], [0, cbrt_2]],
                         backend='normaliz')
P4_normaliz
P5_normaliz = Polyhedron(vertices=[[sqrt_2s, 0], [0, cbrt_2s]],
                         backend='normaliz')
P5_normaliz

The backend normaliz provides other methods such as integral_hull, which also works on unbounded polyhedron.

Sage

sage: # optional - pynormaliz
sage: P6 = Polyhedron(vertices=[[0, 0], [3/2, 0], [3/2, 3/2], [0, 3]],
....:                 backend='normaliz')
sage: IH = P6.integral_hull(); IH
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P6.plot(color='blue') + IH.plot(color='red')
Graphics object consisting of 12 graphics primitives
sage: P1_normaliz.integral_hull()
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

Python

>>> from sage.all import *
>>> # optional - pynormaliz
>>> P6 = Polyhedron(vertices=[[Integer(0), Integer(0)], [Integer(3)/Integer(2), Integer(0)], [Integer(3)/Integer(2), Integer(3)/Integer(2)], [Integer(0), Integer(3)]],
...                 backend='normaliz')
>>> IH = P6.integral_hull(); IH
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
>>> P6.plot(color='blue') + IH.plot(color='red')
Graphics object consisting of 12 graphics primitives
>>> P1_normaliz.integral_hull()
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray

Sage Live

# optional - pynormaliz
P6 = Polyhedron(vertices=[[0, 0], [3/2, 0], [3/2, 3/2], [0, 3]],
                backend='normaliz')
IH = P6.integral_hull(); IH
P6.plot(color='blue') + IH.plot(color='red')
P1_normaliz.integral_hull()

Lecture 3: To every polyhedron, the proper parent class

In order to know all the methods that a polyhedron object has one has to look into its base class:

• Base class for polyhedra: Miscellaneous methods : This is the generic class for Polyhedron related objects.

• Base class for polyhedra over Z

• Base class for polyhedra over Q

• Base class for polyhedra over RDF

Don’t be surprised if the classes look empty! The classes mainly contain private methods that implement some comparison methods: to verify equality and inequality of numbers in the base ring and other internal functionalities.

To get a full overview of methods offered to you, Base class for polyhedra: Miscellaneous methods is the first place you want to go.

Lecture 4: A library of polytopes

There are a lot of polytopes that are readily available in the library, see Library of commonly used, famous, or interesting polytopes. Have a look at them to see if your polytope is already defined!

Sage

sage: A = polytopes.buckyball(); A  # can take long                                 # needs sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in sqrt5 with defining polynomial x^2 - 5
     with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 60 vertices
sage: B = polytopes.cross_polytope(4); B
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
sage: C = polytopes.cyclic_polytope(3,10); C
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 10 vertices
sage: E = polytopes.snub_cube(exact=False); E
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: polytopes.<tab>  # not tested, to view all the possible polytopes

Python

>>> from sage.all import *
>>> A = polytopes.buckyball(); A  # can take long                                 # needs sage.rings.number_field
A 3-dimensional polyhedron
 in (Number Field in sqrt5 with defining polynomial x^2 - 5
     with sqrt5 = 2.236067977499790?)^3
 defined as the convex hull of 60 vertices
>>> B = polytopes.cross_polytope(Integer(4)); B
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
>>> C = polytopes.cyclic_polytope(Integer(3),Integer(10)); C
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 10 vertices
>>> E = polytopes.snub_cube(exact=False); E
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
>>> polytopes.<tab>  # not tested, to view all the possible polytopes

Sage Live

A = polytopes.buckyball(); A  # can take long                                 # needs sage.rings.number_field
B = polytopes.cross_polytope(4); B
C = polytopes.cyclic_polytope(3,10); C
E = polytopes.snub_cube(exact=False); E
polytopes.<tab>  # not tested, to view all the possible polytopes

Bibliography

[Bro1983]

A. Brondsted, An Introduction to Convex Polytopes, volume 90 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1983. ISBN 978-1-4612-7023-2

[Goo2004]

J. E. Goodman and J. O’Rourke, editors, CRC Press LLC, Boca Raton, FL, 2004. ISBN 978-1584883012 (65 chapters, xvii + 1539 pages).

[Gru1967]

B. Grünbaum, Convex polytopes, volume 221 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2003. ISBN 978-1-4613-0019-9

[Zie2007] (1,2)

G. M. Ziegler, Lectures on polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2007. ISBN 978-0-387-94365-7

Make live