/usr/share/polymake/demo/apps

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial on Polytopes\n",
    "\n",
    "**This tutorial is also available as a {{ :tutorial:apps_polytope.ipynb |jupyter notebook}} for polymake 3.1.**\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<sub>0</sub> to 1.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "$p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]);"
   ]
  },
  {
   "attachments": {},
   "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": [
    {
     "data": {
      "text/plain": [
       "1 -1 -1\n",
       "1 1 -1\n",
       "1 -1 1\n",
       "1 1 1\n",
       "\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $p->VERTICES;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also add a lineality space via the input property `INPUT_LINEALITY`.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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]]);"
   ]
  },
  {
   "attachments": {},
   "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;"
   ]
  },
  {
   "attachments": {},
   "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": {},
   "outputs": [],
   "source": [
    "$p3 = new Polytope<Rational>(VERTICES=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]], LINEALITY_SPACE=>[]);"
   ]
  },
  {
   "attachments": {},
   "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<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 [Coordinates for Polyhedra](tutorial/coordinates). Here is an example:\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "$p4 = new Polytope(INEQUALITIES=>[[1,1,0],[1,0,1],[1,-1,0],[1,0,-1],[17,1,1]]);"
   ]
  },
  {
   "attachments": {},
   "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": [
    {
     "data": {
      "text/plain": [
       "0: x1 >= -1\n",
       "1: x2 >= -1\n",
       "2: -x1 >= -1\n",
       "3: -x2 >= -1\n",
       "4: x1 + x2 >= -17\n",
       "\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_constraints($p4->INEQUALITIES);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 1 0\n",
       "1 0 1\n",
       "1 -1 0\n",
       "1 0 -1\n",
       "\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $p4->FACETS;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": {},
   "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]]);"
   ]
  },
  {
   "attachments": {},
   "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": {},
   "outputs": [],
   "source": [
    "prefer \"lrs\";                              # use lrs until revoked by another 'prefer' or 'reset_preference \"lrs\"'\n",
    "$p = new Polytope(POINTS=>[[1,1],[1,0]]);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "polymake: used package lrs\n",
       "  Implementation of the reverse search algorithm of Avis and Fukuda.\n",
       "  Copyright by David Avis.\n",
       "  http://cgm.cs.mcgill.ca/~avis/lrs.html\n",
       "    \n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $p->FACETS;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    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": {},
   "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);"
   ]
  },
  {
   "attachments": {},
   "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": [
    {
     "data": {
      "text/plain": [
       "1 -1 -1\n",
       "1 1 -1\n",
       "1 -1 1\n",
       "1 1 1\n",
       "\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $c1->VERTICES;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": [
    {
     "data": {
      "text/plain": [
       "4\n",
       "\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $c1->VOLUME;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": [
    {
     "data": {
      "text/plain": [
       "1\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print isomorphic($p1x2,cube(4));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0\n",
       "\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print congruent($p1x2,cube(4));"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": [
    {
     "data": {
      "text/plain": [
       "1 -1 -1 -2 -2\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $p1x2->VERTICES->[0];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1 -2 -2 -1 -1\n",
       "\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $p2x1->VERTICES->[0];"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0 0\n",
       "\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $nc->SIMPLE, \" \", $nc->SIMPLICIAL;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": [
    {
     "data": {
      "text/plain": [
       "32 80 72 24\n",
       "\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $nc->F_VECTOR;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": [
    {
     "data": {
      "text/plain": [
       "32 80 80 40 10\n",
       "\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print cube(5)->F_VECTOR;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": [
    {
     "data": {
      "text/plain": [
       "1\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print isomorphic($nc->GRAPH->ADJACENCY,cube(5)->GRAPH->ADJACENCY);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1\n",
       "\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $nc->CUBICAL;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\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": ".pm",
   "mimetype": "text/x-polymake",
   "name": "polymake"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
polymake-common 3.2r2-3 / usr / share / polymake / demo / apps_polytope.ipynb
