user_guide:tutorials:apps_polytope

Differences

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

 user_guide:tutorials:apps_polytope [2019/01/29 21:46]127.0.0.1 external edit user_guide:tutorials:apps_polytope [2019/02/04 22:55] (current) 2019/02/04 14:29 benmuell replace by include2019/01/29 21:46 external edit2019/01/25 13:40 oroehrig ↷ Links adapted because of a move operation2019/01/25 13:32 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:38 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:35 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:35 oroehrig ↷ Page moved from user_guide:apps_polytope to user_guide:tutorials:apps_polytope2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:apps_polytope to user_guide:apps_polytope2017/11/06 08:17 joswig [Tutorial on Polytopes] 2017/06/19 16:26 joswig typo2017/06/19 15:54 benmuell 2017/06/19 15:54 benmuell add notebook2017/05/19 16:19 oroehrig fixed wrong declaration of empty lineality2017/03/25 16:31 oroehrig added section on convex hull computation2017/03/24 15:26 oroehrig [V-Description] added link to visual tutorial2017/03/17 16:10 oroehrig made some small changes to the second part and updated links2017/03/16 14:18 oroehrig refactored first part2014/01/03 15:45 external edit2013/02/26 10:32 herr highlighted semantics of inequalities2012/07/08 10:38 herr [Constructing a polytope from scratch] 2012/07/08 10:37 herr [Constructing a polytope from scratch] 2012/07/08 10:27 herr [Constructing a polytope from scratch] 2012/07/08 10:27 herr [Constructing a polytope from scratch] 2012/07/08 10:26 herr Added comment on encoding of inequalities as rows of a matrix2012/05/16 12:50 paffenholz 2012/05/16 12:47 paffenholz [Constructing a polytope from scratch] 2019/02/04 14:29 benmuell replace by include2019/01/29 21:46 external edit2019/01/25 13:40 oroehrig ↷ Links adapted because of a move operation2019/01/25 13:32 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:38 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:35 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:35 oroehrig ↷ Page moved from user_guide:apps_polytope to user_guide:tutorials:apps_polytope2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:apps_polytope to user_guide:apps_polytope2017/11/06 08:17 joswig [Tutorial on Polytopes] 2017/06/19 16:26 joswig typo2017/06/19 15:54 benmuell 2017/06/19 15:54 benmuell add notebook2017/05/19 16:19 oroehrig fixed wrong declaration of empty lineality2017/03/25 16:31 oroehrig added section on convex hull computation2017/03/24 15:26 oroehrig [V-Description] added link to visual tutorial2017/03/17 16:10 oroehrig made some small changes to the second part and updated links2017/03/16 14:18 oroehrig refactored first part2014/01/03 15:45 external edit2013/02/26 10:32 herr highlighted semantics of inequalities2012/07/08 10:38 herr [Constructing a polytope from scratch] 2012/07/08 10:37 herr [Constructing a polytope from scratch] 2012/07/08 10:27 herr [Constructing a polytope from scratch] 2012/07/08 10:27 herr [Constructing a polytope from scratch] 2012/07/08 10:26 herr Added comment on encoding of inequalities as rows of a matrix2012/05/16 12:50 paffenholz 2012/05/16 12:47 paffenholz [Constructing a polytope from scratch] 2012/05/16 11:24 herr added comment on LINEALITY_SPACE2011/11/23 10:57 herr Links to howto:data changed to tutorial:data2011/02/16 12:44 herr [Constructing a polytope from scratch] 2011/02/16 12:43 herr [Constructing a polytope from scratch] 2011/02/16 10:54 herr Basic construction of a polytope2009/11/03 12:59 sherrmann Links to tutorial:graph_tutorial changed to tutorial:apps_graph2009/11/02 15:06 herr 2009/11/02 14:42 joswig 2009/11/02 14:27 joswig 2009/11/02 14:08 joswig 2009/11/02 14:04 joswig 2009/11/02 14:00 joswig 2009/11/02 13:48 joswig created Line 1: Line 1: - ====== Tutorial on Polytopes ====== + {{page>.:latest:@FILEID@}} - + - **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​ to 1. + - <​code>​ + - polytope > $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: + - <​code>​ + - polytope > 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''​. + - <​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]]);​ + - ​ + - To take a look at what that thing looks like, you can use the ''​VISUAL''​ method: + - <​code>​ + - polytope >$p2->​VISUAL;​ + - ​ + - 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=>​[]);​ + - ​ + - ==== 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​ + a<​sub>​1​ x<​sub>​1​ + ... + a<​sub>​d​ x<​sub>​d​ >= 0 is encoded as a row vector (a<​sub>​0,​a<​sub>​1,​...,​a<​sub>​d​),​ 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]]);​ + - ​ + - 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 + - ​ + - The last inequality means 17+x<​sub>​1​+x<​sub>​2​ <​html>&​ge;​ 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 + - ​ + - + - 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]]);​ + - ​ + - 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 + - ​ + - + - + - ===== 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);​ + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - 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 + - ​ + - + - See the [[apps_graph|tutorial on graphs]] for more on that subject. +
• user_guide/tutorials/apps_polytope.txt