Differences

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

--- user_guide:tutorials:coordinates [2019/01/25 13:40] – ↷ Page moved from user_guide:coordinates to user_guide:tutorials:coordinates oroehrig
+++ user_guide:tutorials:coordinates [2019/02/04 22:55] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
-====== Coordinates for Polyhedra ======
+{{page>.:latest:@FILEID@}}
-  * This page explains how the coordinates for objects of type ''Polytope<Coord>'' in application ''polytope'' work.
-Each polyhedron can be written as the Minkowski sum of a convex polytope (spanned by points //a,b,c,...//) and a cone (generated by the rays //r,s,t,...//). If the polyhedron is bounded, i.e. it is a polytope, then the cone is empty.
-Suppose our polyhedron lives in a //d//-space //V//.
-In order to obtain a unified view on the polytope and the cone section of a polyhedron, we embed V as an affine subspace of a (//d//+1)-space //W// such that the image of //V// contains the point //(1,0,0,...,0)// and it is parallel to the subspace spanned by the last //d// unit vectors.
-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. {{ 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.
-The polytope point //a=(ay,az)// is modelled as the infinite ray from the origin //(0,0,0)// through the point //(1,ay,az)//, i.e. the set of all non-negative multiples of //(1,ay,az)//. The cone point //r=(ry,rz)// becomes the ray through //(0,ry,rz)//.
-The facet containing the points //a// and //c// is represented by an (oriented) normal vector of the (hyper-)plane spanned by //a//, //c//, and the origin. If //d=2//, as in the picture, the normal vector can be computed as the cross product of //a// and //c//. The normal vector will be oriented such that it points towards the interior of the polyhedron.
-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.
-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.
-===== An example =====
-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.