{ "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 x0 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 a0 + a1 x1 + ... + ad xd >= 0 is encoded as a row vector (a0,a1,...,ad), 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+x1+x2 ≥ 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 }