# Differences

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

Both sides previous revision Previous revision Next revision | Previous revision | ||

user_guide:tutorials:coordinates [2019/01/25 10:58] oroehrig ↷ Links adapted because of a move operation |
user_guide:tutorials:coordinates [2019/02/04 22:55] (current) |
||
---|---|---|---|

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; | ||

- | 1 0 0 0 | ||

- | 0 1 0 0 | ||

- | 0 0 1 0 | ||

- | 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; | ||

- | 0 | ||

- | </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. |