user_guide:tutorials:coordinates

Differences

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

Link to this comparison view

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.  
  • user_guide/tutorials/coordinates.txt
  • Last modified: 2019/02/04 22:55
  • (external edit)