user_guide:tutorials:coordinates

# Differences

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

 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) 2019/01/25 13:40 oroehrig ↷ Page moved from user_guide:coordinates to user_guide:tutorials:coordinates2019/01/25 10:58 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:coordinates to user_guide:coordinates2014/04/09 09:15 assarf small fix about the orientation of homogeneous coordinates2014/01/03 15:45 external edit2012/07/08 10:32 herr [An example] 2012/07/08 10:31 herr 2012/07/07 14:41 joswig [An example] 2012/07/07 14:40 joswig 2012/05/16 11:26 herr [Internal treatment of polytope generators (svn version only)] 2011/05/18 07:40 joswig [An example] 2011/05/18 07:36 joswig [An example] 2011/05/18 07:32 joswig [Coordinates for Polyhedra] added example2011/02/17 07:49 paffenholz [Internal treatment of polytope generators] 2011/02/12 00:11 herr [Internal treatment of polytope generators] 2011/02/11 16:57 herr 2011/01/17 09:12 joswig created 2019/01/25 13:40 oroehrig ↷ Page moved from user_guide:coordinates to user_guide:tutorials:coordinates2019/01/25 10:58 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:coordinates to user_guide:coordinates2014/04/09 09:15 assarf small fix about the orientation of homogeneous coordinates2014/01/03 15:45 external edit2012/07/08 10:32 herr [An example] 2012/07/08 10:31 herr 2012/07/07 14:41 joswig [An example] 2012/07/07 14:40 joswig 2012/05/16 11:26 herr [Internal treatment of polytope generators (svn version only)] 2011/05/18 07:40 joswig [An example] 2011/05/18 07:36 joswig [An example] 2011/05/18 07:32 joswig [Coordinates for Polyhedra] added example2011/02/17 07:49 paffenholz [Internal treatment of polytope generators] 2011/02/12 00:11 herr [Internal treatment of polytope generators] 2011/02/11 16:57 herr 2011/01/17 09:12 joswig created 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]]);​ - ​ - - 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 - ​ - - 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 - ​ - - 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} - ​ - - The rays span the //face at infinity//. - <​code>​ - polytope > print $p->​FAR_FACE; ​ ​ - {1 2 3} - ​ - - By the way, unbounded polyhedra can be visualized just like bounded ones. ''​polymake''​ automatically chooses a bounding box. - <​code>​ - polytope >$p->​VISUAL;​ - ​ - ===== 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​=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:​ x<​sub>​0​=0//​. The rays defining the bounded part (R<​sub>​b​) and rays with //​x<​sub>​0​=0//​ (R<​sub>​0​) 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//​. All these rays together with the rays in R<​sub>​b​ and R<​sub>​0​ 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