Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
user_guide:tutorials:apps_polytope [2019/01/29 21:46] – external edit 127.0.0.1 | user_guide:tutorials:apps_polytope [2019/02/04 22:55] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Tutorial on Polytopes ====== | + | {{page>.:latest:@FILEID@}} |
- | + | ||
- | **This tutorial is also available as a {{ user_guide: | + | |
- | + | ||
- | A // | + | |
- | + | ||
- | 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 [[..: | + | |
- | + | ||
- | The second part demonstrates some of the tool '' | + | |
- | + | ||
- | ===== 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 '' | + | |
- | < | + | |
- | polytope > $p = new Polytope(POINTS=> | + | |
- | </ | + | |
- | The '' | + | |
- | < | + | |
- | polytope > print $p-> | + | |
- | 1 -1 -1 | + | |
- | 1 1 -1 | + | |
- | 1 -1 1 | + | |
- | 1 1 1 | + | |
- | </ | + | |
- | You can also add a lineality space via the input property '' | + | |
- | < | + | |
- | polytope > $p2 = new Polytope(POINTS=> | + | |
- | </ | + | |
- | To take a look at what that thing looks like, you can use the '' | + | |
- | < | + | |
- | polytope > $p2-> | + | |
- | </ | + | |
- | See [[visual_tutorial# | + | |
- | + | ||
- | 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 '' | + | |
- | + | ||
- | The input properties '' | + | |
- | < | + | |
- | polytope > $p3 = new Polytope< | + | |
- | </ | + | |
- | ==== 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< | + | |
- | < | + | |
- | polytope > $p4 = new Polytope(INEQUALITIES=> | + | |
- | </ | + | |
- | To display the inequalities in a nice way, use the '' | + | |
- | < | + | |
- | polytope > print_constraints($p4-> | + | |
- | 0: x1 >= -1 | + | |
- | 1: x2 >= -1 | + | |
- | 2: -x1 >= -1 | + | |
- | 3: -x2 >= -1 | + | |
- | 4: x1 + x2 >= -17 | + | |
- | </ | + | |
- | The last inequality means 17+x< | + | |
- | < | + | |
- | polytope > print $p4-> | + | |
- | 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 '' | + | |
- | < | + | |
- | polytope > $p5 = new Polytope(INEQUALITIES=> | + | |
- | </ | + | |
- | Again, if you are sure that all your inequalities are facets, you can use the properties '' | + | |
- | + | ||
- | + | ||
- | ===== Convex Hulls ===== | + | |
- | + | ||
- | Of course, '' | + | |
- | < | + | |
- | polytope > prefer " | + | |
- | polytope > $p = new Polytope(POINTS=> | + | |
- | + | ||
- | polytope > print $p-> | + | |
- | polymake: used package lrs | + | |
- | Implementation of the reverse search algorithm of Avis and Fukuda. | + | |
- | Copyright by David Avis. | + | |
- | http:// | + | |
- | + | ||
- | 1 -1 | + | |
- | 0 1 | + | |
- | </ | + | |
- | + | ||
- | + | ||
- | ===== A Neighborly Cubical Polytope ===== | + | |
- | + | ||
- | '' | + | |
- | + | ||
- | 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 // | + | |
- | + | ||
- | * Joswig & Ziegler: Neighborly cubical polytopes. | + | |
- | + | ||
- | This is the entire construction in a few lines of '' | + | |
- | + | ||
- | < | + | |
- | polytope > $c1 = cube(2); | + | |
- | polytope > $c2 = cube(2, | + | |
- | polytope > $p1x2 = product($c1, | + | |
- | polytope > $p2x1 = product($c2, | + | |
- | polytope > $nc = conv($p1x2, | + | |
- | </ | + | |
- | + | ||
- | Let us examine more closely what this is about. First we constructed a square '' | + | |
- | + | ||
- | < | + | |
- | polytope > print $c1-> | + | |
- | 1 -1 -1 | + | |
- | 1 1 -1 | + | |
- | 1 -1 1 | + | |
- | 1 1 1 | + | |
- | </ | + | |
- | + | ||
- | The four vertices are listed line by line in homogeneous coordinates, | + | |
- | + | ||
- | < | + | |
- | polytope > print $c1-> | + | |
- | 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 '' | + | |
- | + | ||
- | The third command constructs the polytope '' | + | |
- | + | ||
- | < | + | |
- | polytope > print isomorphic($p1x2, | + | |
- | 1 | + | |
- | polytope > print congruent($p1x2, | + | |
- | 0 | + | |
- | </ | + | |
- | + | ||
- | Both return values are boolean, represented by the numbers '' | + | |
- | + | ||
- | The polytope '' | + | |
- | + | ||
- | < | + | |
- | polytope > print $p1x2-> | + | |
- | 1 -1 -1 -2 -2 | + | |
- | polytope > print $p2x1-> | + | |
- | 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. | + | |
- | + | ||
- | < | + | |
- | polytope > print $nc-> | + | |
- | 0 0 | + | |
- | </ | + | |
- | + | ||
- | 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. | + | |
- | + | ||
- | < | + | |
- | polytope > print $nc-> | + | |
- | 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: | + | |
- | + | ||
- | < | + | |
- | polytope > print cube(5)-> | + | |
- | 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. | + | |
- | + | ||
- | < | + | |
- | polytope > print isomorphic($nc-> | + | |
- | 1 | + | |
- | polytope > print $nc-> | + | |
- | 1 | + | |
- | </ | + | |
- | + | ||
- | See the [[apps_graph|tutorial on graphs]] for more on that subject. | + | |