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).
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.
A polytope can be constructed as the convex hull of
finitely many points; the points can be denoted simply
as sequences of integers (or even rational numbers), although
they will be cast as points of an ambient lattice (that is,
a Q-vector space marked with a spanning lattice Z
n).
For example, we build a polytope P as the convex hull
of the four points (1, 0, 0), (0, 1, 0), (1, - 3, 5) and ( - 2, 2, - 5).
> 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);
20
The 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)
}
A ray is a rational half-line Q^ + v from the origin passing
through a point v ∈Q
n.
A cone is the convex hull of finitely many rays.
> 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)
]
[Next][Prev] [Right] [____]
[Up] [Index] [Root]