Table of Contents
Tutorial on Polytopes
A polytope is the convex hull of finitely many points in some Euclidean space. Equivalently, a polytope is the bounded intersection of finitely many affine halfspaces. polymake can deal with polytopes in both representations and provides numerous tools for analysis.
This tutorial first shows basic ways of defining a polytope from scratch. For larger input (e.g. from a file generated by some other program) have a look at our HowTo on loading data in polymake.
The second part demonstrates some of the tool polymake provides for handling polytopes by examining a small example. For a complete list of properties of polytopes and functions that polymake provides, see the polytope documentation.
Constructing a polytope from scratch
V-Description
To define a polytope as the convex hull of finitely many points, you can pass a matrix of coordinates to the constructor. Since polymake uses homogeneous coordinates, you need to set the additional coordinate x0 to 1.
> $p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]);
The POINTS can be any set of coordinates, they are not required to be irredundant nor vertices of their convex hull. To compute the actual vertices of our polytope, we do this:
> print $p->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1
You can also add a lineality space via the input property INPUT_LINEALITY.
> $p2 = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]],INPUT_LINEALITY=>[[0,1,0]]);
To take a look at what that thing looks like, you can use the VISUAL method:
> $p2->VISUAL;
See here for details on visualizing polytopes.
If you are sure that all the points really are extreme points (vertices) and your description of the lineality space is complete, you can define the polytope via the properties VERTICES and LINEALITY_SPACE instead of POINTS and INPUT_LINEALITY. This way, you can avoid unnecessary redundancy checks.
The input properties POINTS / INPUT_LINEALITY may not be mixed with the properties VERTICES / LINEALITY_SPACE. Furthermore, the LINEALITY_SPACE must be specified as soon as the property VERTICES is used:
> $p3 = new Polytope<Rational>(VERTICES=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]], LINEALITY_SPACE=>[]);
H-Description
It is also possible to define a polytope as an intersection of finitely many halfspaces, i.e., a matrix of inequalities.
An inequality a0 + a1 x1 + … + ad xd >= 0 is encoded as a row vector (a0,a1,…,ad), see also Coordinates for Polyhedra. Here is an example:
> $p4 = new Polytope(INEQUALITIES=>[[1,1,0],[1,0,1],[1,-1,0],[1,0,-1],[17,1,1]]);
To display the inequalities in a nice way, use the print_constraints method.
> print_constraints($p4->INEQUALITIES); 0: x1 >= -1 1: x2 >= -1 2: -x1 >= -1 3: -x2 >= -1 4: x1 + x2 >= -17 5: 0 >= -1
The last inequality means 17+x1+x2 >= 0, hence it does not represent a facet of the polytope. If you want to take a look at the actual facets, do this:
> print $p4->FACETS; 1 1 0 1 0 1 1 -1 0 1 0 -1
If your polytope lies in an affine subspace then you can specify its equations via the input property EQUATIONS.
> $p5 = new Polytope(INEQUALITIES=>[[1,1,0,0],[1,0,1,0],[1,-1,0,0],[1,0,-1,0]],EQUATIONS=>[[0,0,0,1],[0,0,0,2]]);
Again, if you are sure that all your inequalities are facets, you can use the properties FACETS and AFFINE_HULL instead. Note that this pair of properties is dual to the pair VERTICES / LINEALITY_SPACE described above.
Convex Hull Computations
Of course, polymake can convert the V-description of a polytope to its H-description and vice versa. In fact, this is done automatically whenever you ask for a suitable property.
For instance, continuing with the example above, the following triggers a dual convex hull computation. Note that this particular command does not compute any output.
> $p5->VERTICES;
Printing the vertices later does not result in a recomputation. Known properties are stored.
> print $p5->VERTICES; 1 1 -1 0 1 1 1 0 1 -1 1 0 1 -1 -1 0
Depending on the individual configuration polymake chooses one of the several convex hull computing algorithms that have a polymake interface. Available algorithms are double description (cdd of ppl), reverse search (lrs), and beneath beyond (internal). It is also possible to specify explicitly which method to use by using the prefer_now command. Here we show a primal convex hull computaton, i.e., from V- to H-description, with lrs.
> prefer_now "lrs"; > $p = new Polytope(POINTS=>[[1,1],[1,0]]); > print $p->FACETS; 1 -1 0 1
Use prefer instead of prefer_now if you want to make this permanent.
A Neighborly Cubical Polytope
polymake provides a variety of standard polytope constructions and transformations. This example construction introduces some of them. Check out the documentation for a comprehensive list.
The goal is to construct a 4-dimensional cubical polytope which has the same graph as the 5-dimensional cube. It is an example of a neighborly cubical polytope as constructed in
- Joswig & Ziegler: Neighborly cubical polytopes. Discrete Comput. Geom. 24 (2000), no. 2-3, 325–344, DOI 10.1007/s004540010039
This is the entire construction in a few lines of polymake code:
> $c1 = cube(2); > $c2 = cube(2,2); > $p1x2 = product($c1,$c2); > $p2x1 = product($c2,$c1); > $nc = conv($p1x2,$p2x1);
Let us examine more closely what this is about. First we constructed a square $c1 via calling the function cube. The only parameter 2 is the dimension of the cube to be constructed. It is not obvious how the coordinates are chosen; so let us check.
> print $c1->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1
The four vertices are listed line by line in homogeneous coordinates, where the homogenizing coordinate is the leading one. As shown the vertices correspond to the four choices of +/-1 in two positions. So the area of this square equals four, which is verified as follows:
> print $c1->VOLUME; 4
Here the volume is the Euclidean volume of the ambient space. Hence the volume of a polytope which is not full-dimensional is always zero.
The second polytope $c2 constructed is also a square. However, the optional second parameter says that +/-2-coordinates are to be used rather than +/-1 as in the default case. The optional parameter is also allowed to be 0. In this case a cube with 0/1-coordinates is returned. You can access the documentation of functions by typing their name in the polymake shell and then hitting F1.
The third command constructs the polytope $p1x2 as the cartesian product of the two squares. Clearly, this is a four-dimensional polytope which is combinatorially (even affinely) equivalent to a cube, but not congruent. This is easy to verify:
> print isomorphic($p1x2,cube(4)); true > print congruent($p1x2,cube(4)); 0
Both return values are boolean, represented by the numbers 1 and 0, respectively. This questions are decided via a reduction to a graph isomorphism problem which in turn is solved via polymake's interface to nauty.
The polytope $p2x1 does not differ that much from the previous. In fact, the construction is twice the same, except for the ordering of the factors in the call of the function product. Let us compare the first vertices of the two products. One can see how the coordinates are induced by the ordering of the factors.
> print $p1x2->VERTICES->[0]; 1 -1 -1 2 -2 > print $p2x1->VERTICES->[0]; 1 2 -2 -1 -1
In fact, one of these two products is obtained from the other by exchanging coordinate directions. Thats is to say, they are congruent but distinct as subsets of Euclidean 4-space. This is why taking their joint convex hull yields something interesting. Let us explore what kind of polytope we got.
> print $nc->SIMPLE, " ", $nc->SIMPLICIAL; false false
This says the polytope is neither simple nor simplicial. A good idea then is to look at the f-vector. Beware, however, this usually requires to build the entire face lattice of the polytope, which is extremely costly. Therefore this is computationally infeasible for most high-dimensional polytopes.
> print $nc->F_VECTOR; 32 80 72 24
This is a first hint that our initial claim is indeed valid. The polytope constructed has 32 vertices and 80 = 32*5/2 edges, as many as the 5-dimensional cube:
> print cube(5)->F_VECTOR; 32 80 80 40 10
What is left is to check whether the vertex-edge graphs of the two polytopes actually are the same, and if all proper faces are combinatorially equivalent to cubes.
> print isomorphic($nc->GRAPH->ADJACENCY,cube(5)->GRAPH->ADJACENCY); true > print $nc->CUBICAL; true
See the tutorial on graphs for more on that subject.