user_guide:tutorials:apps_polytope

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Last revisionBoth sides next revision
user_guide:tutorials:apps_polytope [2019/01/29 21:46] – external edit 127.0.0.1user_guide:tutorials:apps_polytope [2019/02/04 14:29] – replace by include benmuell
Line 1: Line 1:
-====== Tutorial on Polytopes ====== +{{page>.:release:3.3:apps_polytope}}
- +
-**This tutorial is also available as a {{ user_guide:apps_polytope.ipynb |jupyter notebook}} for polymake 3.1.** +
- +
-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  [[..:howto:data|how to load 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 [[reldocs>3.0/polytope.html|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 [[user_guide:tutorials:coordinates|homogeneous coordinates]], you need to set the additional coordinate x<sub>0</sub> to 1. +
-<code> +
-polytope > $p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]); +
-</code> +
-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: +
-<code> +
-polytope > print $p->VERTICES; +
-1 -1 -1 +
-1 1 -1 +
-1 -1 1 +
-1 1 1 +
-</code> +
-You can also add a lineality space via the input property ''INPUT_LINEALITY''. +
-<code> +
-polytope > $p2 = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]],INPUT_LINEALITY=>[[0,1,0]]); +
-</code> +
-To take a look at what that thing looks like, you can use the ''VISUAL'' method: +
-<code> +
-polytope > $p2->VISUAL; +
-</code> +
-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: +
-<code> +
-polytope > $p3 = new Polytope<Rational>(VERTICES=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]], LINEALITY_SPACE=>[]); +
-</code> +
-==== 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 a<sub>0</sub> + a<sub>1</sub> x<sub>1</sub> + ... + a<sub>d</sub> x<sub>d</sub> >= 0 is encoded as a row vector (a<sub>0</sub>,a<sub>1</sub>,...,a<sub>d</sub>), see also [[user_guide:tutorials:coordinates|Coordinates for Polyhedra]]. Here is an example: +
-<code> +
-polytope > $p4 = new Polytope(INEQUALITIES=>[[1,1,0],[1,0,1],[1,-1,0],[1,0,-1],[17,1,1]]); +
-</code> +
-To display the inequalities in a nice way, use the ''print_constraints'' method. +
-<code> +
-polytope > print_constraints($p4->INEQUALITIES); +
-0: x1 >= -1 +
-1: x2 >= -1 +
-2: -x1 >= -1 +
-3: -x2 >= -1 +
-4: x1 + x2 >= -17 +
-</code> +
-The last inequality means 17+x<sub>1</sub>+x<sub>2</sub> <html>&ge;</html> 0, hence it does not represent a facet of the polytope. If you want to take a look at the acutal facets, do this: +
-<code> +
-polytope > print $p4->FACETS; +
-1 1 0 +
-1 0 1 +
-1 -1 0 +
-1 0 -1 +
-</code> +
- +
-If your polytope lies in an affine subspace then you can specify its equations via the input property ''EQUATIONS''.\\ +
-<code> +
-polytope > $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]]); +
-</code> +
-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 Hulls ===== +
- +
-Of course, ''polymake'' can convert the V-description of a polytope to its H-description and vice versa. 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'' command: +
-<code> +
-polytope > prefer "lrs";                              # use lrs until revoked by another 'prefer' or 'reset_preference "lrs"' +
-polytope > $p = new Polytope(POINTS=>[[1,1],[1,0]]); +
- +
-polytope > print $p->FACETS; +
-polymake: used package lrs +
-  Implementation of the reverse search algorithm of Avis and Fukuda. +
-  Copyright by David Avis. +
-  http://cgm.cs.mcgill.ca/~avis/lrs.html +
- +
-1 -1 +
-0 1 +
-</code> +
- +
- +
-===== A Neighborly Cubical Polytope ===== +
- +
-''polymake'' provides a variety of standard polytope constructions and transformations. This example construction introduces some of them. Check out the [[:release_docs:3.0: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: +
- +
-<code> +
-polytope > $c1 = cube(2); +
-polytope > $c2 = cube(2,2); +
-polytope > $p1x2 = product($c1,$c2); +
-polytope > $p2x1 = product($c2,$c1); +
-polytope > $nc = conv($p1x2,$p2x1); +
-</code> +
- +
-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. +
- +
-<code> +
-polytope > print $c1->VERTICES; +
-1 -1 -1 +
-1 1 -1 +
-1 -1 1 +
-1 1 1 +
-</code> +
- +
-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: +
- +
-<code> +
-polytope > print $c1->VOLUME; +
-4 +
-</code> +
- +
-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: +
- +
-<code> +
-polytope > print isomorphic($p1x2,cube(4)); +
-1 +
-polytope > print congruent($p1x2,cube(4)); +
-0 +
-</code> +
- +
-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. +
- +
-<code> +
-polytope > print $p1x2->VERTICES->[0]; +
-1 -1 -1 -2 -2 +
-polytope > print $p2x1->VERTICES->[0]; +
-1 -2 -2 -1 -1 +
-</code> +
- +
-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. +
- +
-<code> +
-polytope > print $nc->SIMPLE, " ", $nc->SIMPLICIAL; +
-0 0 +
-</code> +
- +
-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. +
- +
-<code> +
-polytope > print $nc->F_VECTOR; +
-32 80 72 24 +
-</code> +
- +
-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: +
- +
-<code> +
-polytope > print cube(5)->F_VECTOR; +
-32 80 80 40 10 +
-</code> +
- +
-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. +
- +
-<code> +
-polytope > print isomorphic($nc->GRAPH->ADJACENCY,cube(5)->GRAPH->ADJACENCY); +
-1 +
-polytope > print $nc->CUBICAL; +
-1 +
-</code> +
- +
-See the [[apps_graph|tutorial on graphs]] for more on that subject. +
  • user_guide/tutorials/apps_polytope.txt
  • Last modified: 2019/02/04 22:55
  • by 127.0.0.1