This is a package with tools to build and analyse finite-dimensional, finitely-generated, rational polyhedra. In general a polyhedron is the Minkowski sum of a rational polytope (the compact, convex hull of finitely many rational points) and a cone (the convex hull of finitely many rational half-lines emanating from the origin).
It is important to note that we are discussing only rational polyhedra: their vertices lie in in some finite-dimensional rational vector space L=Qn with the supporting hyperplanes represented in its dual (loosely speaking, all faces have rational gradients). There is a natural lattice in this setup: the integral sublattice Zn of L. This is a lattice only in the sense of being a Z-module; it does not come with a preferred definite quadratic form (or norm), and so, in particular, lengths of vectors are not defined. (We explain below how volumes are nevertheless defined relative to the integral lattice.) A point of L is called `integral' if it lies in the integral sublattice, but there is no requirement that vertices of polyhedra be integral. Notwithstanding all these remarks, we refer to such ambient spaces L as `lattices'.
This chapter is organised so that functions applying to compact polyhedra, namely polytopes, are collected together in coherent blocks as much as possible. Section Polytopes, Cones and Polyhedra lists various ways of constructing polytopes, cones and polyhedra, including Minkowski sum and other arithmetical and set-theoretical operations. Section Making New Databases presents the basic combinatorics associated to all polyhedra such as recovering their vertices or faces. The next section, Section Making New Databases, is dedicated to polytopes. Most of the functions described here rely on compactness; they include enumeration of points and triangulation. Then Section Making New Databases details functions that apply to polyhedra more generally, although this includes some functions that apply to cones in particular: computing the integral generators of C∩Zn as a semigroup, for example, where C is a cone in L. Finally, there is section outlining the functions that operate on the ambient lattices. These functions are not usually required, since for the most part the ambient space is a book-keeping device that the package handles automatically, but they arise as domains and codomains of maps. This provides a mechanism for modifying the integral sublattice, which can be used to change the underlying notion of which points count as integral.
Before starting, we outline the capabilities of the package by extended examples. The first illustrates the basic machinery available for the analysis of polytopes---that is, the compact convex hulls of finitely many points.
Our second example illustrates the machinery available for cones and polyhedra more generally.
> P := Polytope([ [0,0,0], [1,0,0], [0,1,0], [1,-3,5], [-2,2,-5] ]);
> P;
3-dimensional polytope P with 5 generators:
( 0, 0, 0),
( 1, 0, 0),
( 0, 1, 0),
( 1, -3, 5),
(-2, 2, -5)
No analysis of P has been carried out in its construction.
In fact, one of its defining `generators' is not required,
as can be seen from the vertices of P (which after this
calculation will set as the default printing information).
> Vertices(P);
[
(1, 0, 0),
(0, 1, 0),
(1, -3, 5),
(-2, 2, -5)
]
> P;
3-dimensional polytope P with 4 vertices:
( 1, 0, 0),
( 0, 1, 0),
( 1, -3, 5),
(-2, 2, -5)
One can extract the combinatorial components of P.
Here we recover the facets of P, its faces of codimension 1,
each of which is regarded as a polytope in its own right.
> Facets(P);
[
2-dimensional polytope with 3 vertices:
( 1, -3, 5),
(-2, 2, -5),
( 0, 1, 0),
2-dimensional polytope with 3 vertices:
( 1, -3, 5),
(-2, 2, -5),
( 1, 0, 0),
2-dimensional polytope with 3 vertices:
(1, -3, 5),
(0, 1, 0),
(1, 0, 0),
2-dimensional polytope with 3 vertices:
(-2, 2, -5),
( 0, 1, 0),
( 1, 0, 0)
]
Computing the (integral) points contained in a
polytope (including points on its boundary) is
one of the principal operations for polytopes.
> Points(P);
[
(-2, 2, -5),
(0, 0, 0),
(0, 1, 0),
(1, -3, 5),
(1, 0, 0)
]
The interior points or boundary points can be retrieved
separately using InteriorPoints(P) and BoundaryPoint(P).
One can also compute the volume of a polytope.
> Volume(P); 20The volume is the lattice-normalised volume: (Vol)(P) = n! x (vol)(P), where (vol)(P) is the Euclidean volume of P.
The polar, or dual, to P can be computed.
> D := Polar(P);
> D;
3-dimensional polytope D with 4 vertices:
( 3, -1, -7/5),
(-1, 3, 9/5),
(-1, -1, 1/5),
(-1, -1, -3/5)
The polar of P is again a polytope in this case (simply
because the origin lies in the strict interior of P),
although its vertices need not be integral.
The Ehrhart series,
(Ehr)D(t) = Σn≥0 # ( nD ∩Zn ) tn,
computes the number of points in multiples of a polytope D.
> EhrhartCoefficients(D,10); [ 1, 7, 33, 91, 193, 355, 585, 899, 1309, 1827, 2469 ]The (infinite) Ehrhart series can be recovered as a rational function.
> E<t> := EhrhartSeries(D);
> E;
(t^7 + 4*t^6 + 15*t^5 + 12*t^4 + 12*t^3 + 15*t^2 + 4*t + 1)/(t^8 - 3*t^7 + 3*t^6
- t^5 - t^3 + 3*t^2 - 3*t + 1)
It is possible to make maps of the underlying lattices
and apply them to polyhedra.
> L := Ambient(P);
> K := Quotient(L![1,2,3]);
> K;
2-dimensional toric lattice K = (Z^3) / <1, 2, 3>
> f := LatticeMap(L, K, Matrix(3,2,[1,0,0,1,0,0]));
> Q := Image(f,P);
> Vertices(Q);
[
(1, 0),
(0, 1),
(1, -3),
(-2, 2)
]
In this case the image polytope Q=f(P) is not a simplex.
We can triangulate it.
> Triangulation(Q);
{
2-dimensional polytope with 3 vertices:
(1, 0),
(1, -3),
(0, 1)
2-dimensional polytope with 3 vertices:
(1, -3),
(-2, 2),
(0, 1)
}
> C := Cone([[2,2],[1,1/2]]);
> C;
Cone C with 2 generators:
( 2, 2),
( 1, 1/2)
Although any non-zero point on a ray is enough to define it,
often the non-zero integral point nearest the origin
is preferred. As with polytopes, there is no analysis of
a cone C on its construction, but the minimal generators
are displayed once some function has forced their
calculation.
> Rays(C);
[
(1, 1),
(2, 1)
]
> C;
2-dimensional simplicial cone C with 2 minimal generators:
(1, 1),
(2, 1)
A polyhedron is the Minkowski sum (simply denoted by a plus sign)
of a polytope and a cone.
> P := StandardSimplex(2);
> P + C;
2-dimensional polyhedron with 2-dimensional finite part with 3
vertices:
(1, 0),
(0, 1),
(0, 0)
and 2-dimensional infinite part given by a cone with 2 minimal
generators:
(2, 1),
(1, 1)
The polyhedron P + C is now subject to standard combinatorial
analysis, such as computing its facets; some of these may
be (compact) polytopes, while others may themselves be
polyhedra described as the sum of a compact, or finite, part
and a cone, or infinite part.
> Facets(P + C);
[
1-dimensional polytope with 2 vertices:
(1, 0),
(0, 0),
1-dimensional polyhedron with 0-dimensional finite part with one
vertex:
(0, 1)
and 1-dimensional infinite part given by a cone with one minimal
generator:
(1, 1),
1-dimensional polytope with 2 vertices:
(0, 1),
(0, 0),
1-dimensional polyhedron with 0-dimensional finite part with one
vertex:
(1, 0)
and 1-dimensional infinite part given by a cone with one minimal
generator:
(2, 1)
]