====== 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 [[data|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 [[documentation:latest:polytope|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 [[coordinates|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; p2_bounded
Transparency
depthWrite
Rotation
x-axis
y-axis
z-axis
Rotation speed
Display
Objects
Camera
SVG
Download
New tab
See [[visual_tutorial#application_polytope|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(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|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 ([[http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html|cdd]] of [[http://bugseng.com/products/ppl|ppl]]), reverse search ([[http://cgm.cs.mcgill.ca/~avis/C/lrs.html|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:latest:polytope|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, [[http://www.springerlink.com/content/m73pqv6kr80rw4b1/|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 [[apps_graph|tutorial on graphs]] for more on that subject.