{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tutorial on Polytopes\n",
"\n",
"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.\n",
"\n",
"\n",
"\n",
"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](data) in `polymake`.\n",
"\n",
"\n",
"\n",
"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](reldocs>3.0/polytope.html).\n",
"\n",
"## Constructing a polytope from scratch\n",
"\n",
"### V-Description\n",
"\n",
"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](tutorial/coordinates), you need to set the additional coordinate x_{0} to 1.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"$p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"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:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $p->VERTICES;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"You can also add a lineality space via the input property `INPUT_LINEALITY`.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"$p2 = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]],INPUT_LINEALITY=>[[0,1,0]]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"To take a look at what that thing looks like, you can use the `VISUAL` method:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"$p2->VISUAL;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"See [here](visual_tutorial#application polytope) for details on visualizing polytopes.\n",
"\n",
" 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.\n",
"\n",
"\n",
"\n",
" 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:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"$p3 = new Polytope(VERTICES=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]], LINEALITY_SPACE=>[]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### H-Description\n",
"\n",
"It is also possible to define a polytope as an intersection of finitely many halfspaces, i.e., a matrix of inequalities.\n",
"\n",
"\n",
"\n",
"An inequality a_{0} + a_{1} x_{1} + ... + a_{d} x_{d} >= 0 is encoded as a row vector (a_{0},a_{1},...,a_{d}), see also [Coordinates for Polyhedra](tutorial/coordinates). Here is an example:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"$p4 = new Polytope(INEQUALITIES=>[[1,1,0],[1,0,1],[1,-1,0],[1,0,-1],[17,1,1]]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"To display the inequalities in a nice way, use the `print_constraints` method.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print_constraints($p4->INEQUALITIES);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"The last inequality means 17+x_{1}+x_{2} ≥ 0, hence it does not represent a facet of the polytope. If you want to take a look at the acutal facets, do this:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $p4->FACETS;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"If your polytope lies in an affine subspace then you can specify its equations via the input property `EQUATIONS`.\n",
"\n",
"\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"$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]]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"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.\n",
"\n",
"\n",
"\n",
"\n",
"## Convex Hulls\n",
"\n",
"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 ([cdd](http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html) of [ppl](http://bugseng.com/products/ppl)), reverse search ([lrs](http://cgm.cs.mcgill.ca/~avis/C/lrs.html)), and beneath beyond (internal). It is also possible to specify explicitly which method to use by using the `prefer` command:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"prefer \"lrs\"; # use lrs until revoked by another 'prefer' or 'reset_preference \"lrs\"'\n",
"$p = new Polytope(POINTS=>[[1,1],[1,0]]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $p->FACETS;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" \n",
" 1 -1\n",
" 0 1\n",
"\n",
"\n",
"\n",
"## A Neighborly Cubical Polytope\n",
"\n",
"`polymake` provides a variety of standard polytope constructions and transformations. This example construction introduces some of them. Check out the [documentation](/release_docs/3.0/polytope) for a comprehensive list.\n",
"\n",
"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\n",
"\n",
"\n",
"* Joswig & Ziegler: Neighborly cubical polytopes. Discrete Comput. Geom. 24 (2000), no. 2-3, 325--344, [DOI 10.1007/s004540010039](http://www.springerlink.com/content/m73pqv6kr80rw4b1/)\n",
"\n",
"This is the entire construction in a few lines of `polymake` code:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"$c1 = cube(2);\n",
"$c2 = cube(2,2);\n",
"$p1x2 = product($c1,$c2);\n",
"$p2x1 = product($c2,$c1);\n",
"$nc = conv($p1x2,$p2x1);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $c1->VERTICES;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $c1->VOLUME;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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.\n",
"\n",
"\n",
"\n",
"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.\n",
"\n",
"\n",
"\n",
"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:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print isomorphic($p1x2,cube(4));"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print congruent($p1x2,cube(4));"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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`.\n",
"\n",
"\n",
"\n",
"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.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $p1x2->VERTICES->[0];"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $p2x1->VERTICES->[0];"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"print $nc->SIMPLE, \" \", $nc->SIMPLICIAL;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $nc->F_VECTOR;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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:\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print cube(5)->F_VECTOR;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"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.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print isomorphic($nc->GRAPH->ADJACENCY,cube(5)->GRAPH->ADJACENCY);"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print $nc->CUBICAL;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"See the [tutorial on graphs](apps_graph) for more on that subject.\n",
"\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "polymake",
"language": "polymake",
"name": "polymake"
},
"language_info": {
"codemirror_mode": "perl",
"file_extension": ".pl",
"mimetype": "text/x-polymake",
"name": "polymake"
}
},
"nbformat": 4,
"nbformat_minor": 2
}