.. -*- coding: utf-8 -*-
.. linkall
.. _lectures:
=========================================================
A Longer Introduction to Polyhedral Computations in Sage
=========================================================
.. MODULEAUTHOR:: 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).
.. contents:: Lectures Menu
:depth: 2
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:
.. MATH::
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
.. MATH::
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 :code:`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 :ref:`sage.geometry.polyhedron.constructor`.
`V`-representation
------------------------
First, let's define a polyhedron object as the convex hull of a set of points
and some rays.
::
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
.. end of output
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 :ref:`sage.geometry.polyhedron.parent`)
- the number of vertices
- the number of rays
Of course, you want to know what this object looks like:
::
sage: P1.plot()
Graphics object consisting of 5 graphics primitives
.. end of output
We can also add a lineality space.
::
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
.. end of output
Notice that the base ring changes because of the value `\frac{1}{2}`.
Indeed, Sage finds an appropriate ring to define the object.
::
sage: P1.parent()
Polyhedra in QQ^2
sage: P2.parent()
Polyhedra in QQ^3
.. end of output
The chosen ring depends on the input format.
::
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
.. end of output
.. WARNING::
The base ring :code:`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 :code:`RDF`.
::
sage: D = polytopes.dodecahedron()
sage: D
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: D_RDF = Polyhedron(vertices = [n(v.vector(),digits=6) for v in D.vertices()], base_ring=RDF)
Traceback (most recent call last):
...
ValueError: *Error: Numerical inconsistency is found. Use the GMP exact arithmetic.
.. end of output
If the input of the polyhedron consists of python :code:`float`, it
automatically converts the data to :code:`RDF`:
::
sage: Polyhedron(vertices=[[float(1.1)]])
A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex
.. end of output
It is also possible to define polyhedron over algebraic numbers.
::
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
.. end of output
There is another way to create a polyhedron over algebraic numbers:
::
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
.. end of output
If the base ring is known it may be a good option to use the proper :meth:`sage.rings.number_field.number_field.number_field.composite_fields`:
::
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
.. end of output
Polyhedral computations with the :code:`Symbolic Ring` are not implemented.
It is not possible to define a polyhedron over it:
::
sage: sqrt_2s = sqrt(2)
sage: cbrt_2s = 2^(1/3)
sage: Polyhedron(vertices = [[sqrt_2s, 0], [0, cbrt_2s]])
Traceback (most recent call last):
...
ValueError: no default backend for computations with Symbolic Ring
.. end of output
Similarly, it is not possible to create polyhedron objects over :code:`RR`
(no matter how many bits of precision).
::
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'
.. end of output
There is one exception, when the number of bits of precision is 53, then the
base ring is converted to :code:`RDF`:
::
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'>
.. end of output
This behavior can be seen as wrong, but it allows the following to be
acceptable by 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
.. end of output
without having specified the base ring :code:`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: 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
.. end of output
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 :code:`P1` is
defined. The `H`-representation may contain equations:
::
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)
.. end of output
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 :code:`[b_i,a_i1, ..., a_id]`.
::
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))
.. end of output
It is worth using the parameter :code:`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: 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
.. end of output
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: 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
.. end of output
It is possible to obtain the different objects of the `H`-representation
as follows.
::
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)
.. end of output
.. NOTE ::
It is recommended to use :code:`equations` or :code:`equation_generator`
(and similarly for inequalities) if one wants to iterate over them instead
of :code:`equations_list`.
`V`-representation
------------------
Similarly, you can access vertices, rays and lines of the polyhedron.
::
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)
.. end of output
It is possible to obtain the different objects of the `V`-representation
as follows.
::
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]
.. end of output
.. NOTE ::
It is recommended to use :code:`vertices` or :code:`vertex_generator`
(and similarly for rays and lines) if one wants to iterate over them instead
of :code:`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.
- :ref:`sage.geometry.polyhedron.backend_cdd`
- `The cdd and cddplus homepage <https://www.inf.ethz.ch/personal/fukudak/cdd_home/>`_
- :ref:`sage.geometry.polyhedron.backend_ppl`
- `The Parma Polyhedra Library homepage <http://bugseng.com/products/ppl/>`_
- :ref:`sage.geometry.polyhedron.backend_polymake`
- `The polymake project for convex geometry <https://polymake.org>`_
- :ref:`sage.geometry.polyhedron.backend_field`
- This is a :code:`python` backend that provides an implementation of
polyhedron over irrational coordinates.
- :ref:`sage.geometry.polyhedron.backend_normaliz`, (requires the optional package :code:`pynormaliz`)
- `Normaliz Homepage <https://www.normaliz.uni-osnabrueck.de/>`_
The default backend is :code:`ppl`. Whenever one needs **speed** it is good to try out
the different backends. The backend :code:`field` is **not** specifically designed
for dealing with extremal computations but can do computations in exact
coordinates.
The :code:`cdd` backend
-----------------------
In order to use a specific backend, we specify the :code:`backend` parameter.
::
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
.. end of output
A priori, it seems that nothing changed, but ...
::
sage: P1_cdd.parent()
Polyhedra in QQ^2
.. end of output
The polyhedron :code:`P1_cdd` is now considered as a rational polyhedron by the
backend :code:`cdd`. We can also check the backend and the parent using
:code:`type`:
::
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'>
.. end of output
We see
- the backend used (ex: :code:`backend_cdd`)
- followed by a dot '.'
- the parent (ex: :code:`Polyhedra_QQ`) followed again by the backend,
and you can safely ignore the rest for the purpose of this tutorial.
The :code:`cdd` backend accepts also entries in :code:`RDF`:
::
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
.. end of output
but not algebraic or symbolic values:
::
sage: P4_cdd = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]], backend='cdd')
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')
Traceback (most recent call last):
...
ValueError: No such backend (=cdd) implemented for given basering (=Symbolic Ring).
.. end of output
It is possible to get the :code:`cdd` format of any polyhedron object defined
over `\mathbb{Z}`, `\mathbb{Q}`, or :code:`RDF`:
::
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
.. end of output
You can also write this data to a file using the method :code:`.write_cdd_Hrepresentation(filename)`
or :code:`.write_cdd_Vrepresentation(filename)`, where :code:`filename` is a
string containing a path to a file to be written.
The :code:`ppl` backend
-----------------------
The default backend for polyhedron objects is :code:`ppl`.
::
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'>
.. end of output
As you see, it does not accepts values in :code:`RDF` and the polyhedron constructor
used the :code:`cdd` backend.
The :code:`polymake` backend
----------------------------
The :code:`polymake` backend is provided when the experimental package polymake
for sage is installed.
::
sage: p = Polyhedron(vertices=[(0,0),(1,0),(0,1)], # optional - polymake
....: rays=[(1,1)], lines=[],
....: backend='polymake', base_ring=QQ)
.. end of output
An example with quadratic field:
::
sage: V = polytopes.dodecahedron().vertices_list()
sage: Polyhedron(vertices=V, backend='polymake') # optional - polymake
A 3-dimensional polyhedron in (Number Field in sqrt5 with defining polynomial x^2 - 5)^3 defined as the convex hull of 20 vertices
.. end of output
The :code:`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 :code:`field` provides the necessary tools to deal with such
examples.
::
sage: type(D)
<class 'sage.geometry.polyhedron.parent.Polyhedra_field_with_category.element_class'>
.. end of output
Any time that the coordinates should be in an extension of the rationals, the
backend :code:`field` is called.
::
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'>
.. end of output
The :code:`normaliz` backend
----------------------------
The fourth backend is :code:`normaliz` and is an optional Sage package.
::
sage: P1_normaliz = Polyhedron(vertices = [[1, 0], [0, 1]], rays = [[1, 1]], backend='normaliz') # optional - pynormaliz
sage: type(P1_normaliz) # optional - pynormaliz
<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]], # optional - pynormaliz
....: rays = [[1, 1, 0]],
....: lines = [[0, 0, 1]], backend='normaliz')
sage: type(P2_normaliz) # optional - pynormaliz
<class 'sage.geometry.polyhedron.parent.Polyhedra_QQ_normaliz_with_category.element_class'>
.. end of output
This backend does not work with :code:`RDF` or other inexact fields.
::
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).
.. end of output
The :code:`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: P4_normaliz = Polyhedron(vertices = [[sqrt_2, 0], [0, cbrt_2]], backend='normaliz') # optional - pynormaliz
sage: P4_normaliz # optional - pynormaliz
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') # optional - pynormaliz
sage: P5_normaliz # optional - pynormaliz
A 1-dimensional polyhedron in (Symbolic Ring)^2 defined as the convex hull of 2 vertices
.. end of output
The backend :code:`normaliz` provides other methods such as
:code:`integral_hull`, which also works on unbounded polyhedron.
::
sage: P6 = Polyhedron(vertices = [[0, 0], [3/2, 0], [3/2, 3/2], [0, 3]], backend='normaliz') # optional - pynormaliz
sage: IH = P6.integral_hull(); IH # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: P6.plot(color='blue')+IH.plot(color='red') # optional - pynormaliz
Graphics object consisting of 12 graphics primitives
sage: P1_normaliz.integral_hull() # optional - pynormaliz
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 1 ray
.. end of output
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 :code:`base class`:
- :ref:`sage.geometry.polyhedron.base` : This is the generic class for Polyhedron related objects.
- :ref:`Base class for polyhedra over Z <sage.geometry.polyhedron.base_ZZ>`
- :ref:`Base class for polyhedra over Q <sage.geometry.polyhedron.base_QQ>`
- :ref:`sage.geometry.polyhedron.base_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, :ref:`sage.geometry.polyhedron.base` 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
:ref:`sage.geometry.polyhedron.library`. Have a look at them to see if your
polytope is already defined!
::
sage: A = polytopes.buckyball(); A # can take long
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
.. end of output
Bibliography
=============
.. [Bro1983] Brondsted, A., 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] Grünbaum, B., Convex polytopes, volume 221 of Graduate Texts in
Mathematics. Springer-Verlag, New York, 2003. ISBN
978-1-4613-0019-9
.. [Zie2007] Ziegler, G. M., Lectures on polytopes, volume 152 of Graduate
Texts in Mathematics. Springer-Verlag, New York, 2007.
ISBN 978-0-387-94365-7