Differences

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

--- tutorial:coordinates [2011/02/11 16:57] – herr
+++ user_guide:tutorials:coordinates [2019/01/25 13:40] – ↷ Page moved from user_guide:coordinates to user_guide:tutorials:coordinates oroehrig
@@ Line 11: / Line 11: @@
 Points from both sections can now be identified with infinite rays through the origin in //W//. Facets are identified with the a hyperplane containing the image of the facet in //V// and the origin in //W//. This hyperplane is represented by a normal vector.
-Note that a facet defining hyperplane is not uniquely determined if the polyhedron is not full-dimensional. {{ tutorial:coord.gif?326|}}
+Note that a facet defining hyperplane is not uniquely determined if the polyhedron is not full-dimensional. {{ user_guide:coord.gif?326|}}
 A vertex is incident with a facet if and only if the scalar product of their representatives in //W// is zero.
@@ Line 22: / Line 22: @@
 According to this model two points in //W// are identical to polymake if they differ by a positive multiple. In particular, for a polytope point in the input data it is not required that the first coordinate is //1//; it just has to be some positive number.
-polymake is not able to handle unbounded polyhedra which contain an affine line. The combinatorial structure of such not pointed polyhedra cannot be embedded into the combinatorial structure of some bounded polytope. A polyhedron is not of this kind if and only if there is a linear transformation of W that maps the polyhedron to a bounded polytope. In this case there is a unique minimal representation of the polyhedron as the Minkowski sum of a polytope and a cone. polymake treats all the points (= rays) of this minimal representation as vertices.
+Up to and including version 2.9.9 polymake was not able to handle unbounded polyhedra which contain an affine line.  Starting from version 2.10 this is possible.  Notice, however, that **by definition** the combinatorics (encoded as VERTICES_IN_FACETS) of an arbitrary polyhedron is the combinatorics of a polytope which is projectively equivalent to quotient of the orginal polyhedron modulo its lineality space.
-===== Internal treatment of polytope generators =====
+===== An example =====
-As described above polyhedra in ''polymake'' are modelled as the intersection of a cone with the affine hyperplane defined by //x<sub>0</sub>=1//. Hence, infinitely many cones give rise to the same polytope. The algorithms in ''polymake'' usually work with the //homogenized cone// ''homog(P)'' of a polyhedron. Hence, ''polymake'' takes care about the correct canonicalization of user input of polytope generators in the following way:\\ In order to construct ''homog(P)'', the cone defining the polyhedron is intersected with the hyperplane //H<sub>0</sub>: x<sub>0</sub>=0//. The rays defining the bounded part (R<sub>b</sub>) and rays with //x<sub>0</sub>=0// (R<sub>0</sub>) are just inherited. To obtain the rest of the generators for the unbounded part, it is necessary to carry out a "dual Fourier-Motzkin procedure": Any two rays with different signs are linearly combined to a new ray that is contained in //H<sub>0</sub>//. All these rays together with the rays in (R<sub>b</sub>) and (R<sub>0</sub>) then define the //homogenized cone// ''homog(P)''.
+The following defines the positive orthant in 3-space.  It has only one vertex, the origin, and three rays pointing into the three coordinate directions.  The distinction between these comes from our choice of the homogenizing coordinate.
+<code>
+polytope > $p=new Polytope(POINTS=>[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]);
+</code>
+This lists the facet coordinates.
+<code>
+polytope > print $p->FACETS;
+0 0 0
+1 0 0
+0 1 0
+0 0 1
+</code>
+Each line describes one linear inequality.  The encoding is as follows: (a_0,a_1,...,a_d) is the inequality a_0 + a_1 x_1 + ... + a_d x_d >= 0.  This way a point in (oriented) homogeneous coordinates satisfies an inequality if and only if the scalar product of the point with the inequality gives a non-negative value. (Use the command ''print_constraints($m)'' to display the inequalities of the matrix ''$m'' in a nice way.)
+Clearly, the polyhedron is unbounded.
+<code>
+polytope > print $p->BOUNDED;
+</code>
+Yet, the combinatorial data describe a 3-simplex.
+<code>
+polytope > print $p->VERTICES_IN_FACETS;
+{1 2 3}
+{0 2 3}
+{0 1 3}
+{0 1 2}
+</code>
+The rays span the //face at infinity//.
+<code>
+polytope > print $p->FAR_FACE;
+{1 2 3}
+</code>
+By the way, unbounded polyhedra can be visualized just like bounded ones.  ''polymake'' automatically chooses a bounding box.
+<code>
+polytope > $p->VISUAL;
+</code>
+===== Internal treatment of polytope generators =====
+As described above polyhedra in ''polymake'' are modelled as the intersection of a cone with the affine hyperplane defined by //x<sub>0</sub>=1//. Hence, infinitely many cones give rise to the same polytope. The algorithms in ''polymake'' usually work with the //homogenized cone// ''homog(P)'' of a polyhedron. Hence, ''polymake'' takes care about the correct canonicalization of user input of polytope generators in the following way:\\ In order to construct ''homog(P)'', the cone defining the polyhedron is intersected with the hyperplane //H<sub>0</sub>: x<sub>0</sub>=0//. The rays defining the bounded part (R<sub>b</sub>) and rays with //x<sub>0</sub>=0// (R<sub>0</sub>) are just inherited. To obtain the rest of the generators for the unbounded part, it is necessary to carry out a "dual Fourier-Motzkin procedure": Any two rays with different signs are linearly combined to a new ray that is contained in //H<sub>0</sub>//. All these rays together with the rays in R<sub>b</sub> and R<sub>0</sub> then define the //homogenized cone// ''homog(P)''.
+Until version 2.9.9 input generators with a negative first coordinate are just multiplied by -1.