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
tutorial:coordinates [2011/05/18 07:40] – [An example] joswiguser_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. {{ tutorial: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> 
- 
-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 (svn version only) ===== 
-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.1305704434.txt.gz
  • Last modified: 2014/01/03 15:45
  • (external edit)