user_guide:tutorials:polytope_semantics

# Differences

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

 user_guide:tutorials:polytope_semantics [2019/01/25 09:27]oroehrig ↷ Page moved from tutorial:polytope_semantics to user_guide:polytope_semantics user_guide:tutorials:polytope_semantics [2019/02/04 22:55] (current) 2019/01/25 13:40 oroehrig ↷ Page moved from user_guide:polytope_semantics to user_guide:tutorials:polytope_semantics2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:polytope_semantics to user_guide:polytope_semantics2017/07/18 16:02 oroehrig [Special Cases] 2017/07/18 16:00 oroehrig added code2017/03/29 14:04 hnagel [Special Cases] 2014/01/03 15:45 external edit2011/12/19 14:40 paffenholz [Special Cases] 2011/11/23 17:56 joswig moved case distinction for VERTICES to extra paragraph2011/11/23 17:53 joswig [Special Cases] 2011/11/23 15:25 assarf [General Remarks] explained the difference between undef. empty or not-existant2011/11/21 19:09 joswig [Special Cases] 2011/11/21 15:47 assarf [Without coordinates: Combinatorics] there was a ")" too mutch2011/11/21 15:36 joswig [Special Cases] 2011/11/21 15:35 joswig [With coordinates: Geometry] 2011/11/21 15:34 joswig [General Remarks] 2011/11/21 15:33 joswig [Without coordinates: Combinatorics] 2011/11/21 15:32 joswig [Special Cases] 2011/11/21 15:31 joswig [Objects of type ''Polytope''] 2011/11/21 15:27 joswig created 2019/01/25 13:40 oroehrig ↷ Page moved from user_guide:polytope_semantics to user_guide:tutorials:polytope_semantics2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:polytope_semantics to user_guide:polytope_semantics2017/07/18 16:02 oroehrig [Special Cases] 2017/07/18 16:00 oroehrig added code2017/03/29 14:04 hnagel [Special Cases] 2014/01/03 15:45 external edit2011/12/19 14:40 paffenholz [Special Cases] 2011/11/23 17:56 joswig moved case distinction for VERTICES to extra paragraph2011/11/23 17:53 joswig [Special Cases] 2011/11/23 15:25 assarf [General Remarks] explained the difference between undef. empty or not-existant2011/11/21 19:09 joswig [Special Cases] 2011/11/21 15:47 assarf [Without coordinates: Combinatorics] there was a ")" too mutch2011/11/21 15:36 joswig [Special Cases] 2011/11/21 15:35 joswig [With coordinates: Geometry] 2011/11/21 15:34 joswig [General Remarks] 2011/11/21 15:33 joswig [Without coordinates: Combinatorics] 2011/11/21 15:32 joswig [Special Cases] 2011/11/21 15:31 joswig [Objects of type ''Polytope''] 2011/11/21 15:27 joswig created Line 1: Line 1: - ===== Semantics of Cones and Polytopes ===== + {{page>.:latest:@FILEID@}} - + - ==== General Remarks ==== + - + - The general semantics of a [[https://​polymake.org/​doku.php/​howto/​lingo#​big_object | big object]] in polymake is as follows: a list of properties describes an equivalence class of mathematical objects. ​ Often this equivalence class consists of a single element, but this is not necessary. + - + - As an example an object of class [[https://​polymake.org/​release_docs/​latest/​polytope.html#​polytope__Polytope__9|Polytope]] defined by ''​VERTICES''​ gives such a single element equivalence class. ​ A typical example of a class with several elements is a polytope given combinatorially,​ in terms of ''​VERTICES_IN_FACETS''​. ​ An extreme case would be a Polytope object defined by ''​VOLUME''​ only, defining the set of polytopes of all possible dimensions which happen to have that volume. ​ While this  is not very useful, a similar example would be a Polytope object defined by ''​F_VECTOR''​ only.  From this it makes sense to derive, e.g., ''​N_VERTICES''​ or ''​H_VECTOR''​. + - + - All big objects are immutable as mathematical objects. ​ This means it is possible to add more properties, but only consistent ones.  Ideally, these properties pre-exist (since they are logically derived from the input description of the object), and the rules only make them explicit. If a user asks for a property which cannot be derived, this property is set to ''​undef''​. ​ This occurs, e.g., if one asks for the ''​VERTICES''​ of a combinatorially defined polytope. + - + - To view the list properties that currently constitute your object, you can use the ''​properties''​ method. + - <​code>​polytope > $p = new Polytope(POINTS=>​[[1,​2],​[1,​3]]);​ + - + - polytope >$p->​properties;​ + - name: p + - type: Polytope<​Rational>​ + - + - POINTS + - 1 2 + - 1 3 + - + - + - CONE_AMBIENT_DIM + - 2 + - ​ + - + - ===== Objects of type ''​Polytope''​ ===== + - + - Polytope theory is nice because this is where combinatorics meets metric geometry. ​ For mathematical software dealing with such objects it is necessary to get the semantics straight. Below we describe some pitfalls. + - + - ==== With coordinates:​ Geometry ==== + - + - Being non-empty is recorded in the property ''​FEASIBLE''​. This is ''​true''​ if and only if the polytope is not empty. + - <​code>​ + - polytope > print cube(3)->​FEASIBLE;​ + - 1 + - ​ + - + - A non-empty polytope in R^n is encoded as its homogenization in R^{n+1}.  Hence, any non-empty polytope has at least one facet (which may be the far hyperplane [1,​0,​0,​...,​0]) and one vertex. + - + - + - ==== Without coordinates:​ Combinatorics ==== + - + - ''​VERTICES_IN_FACETS''​ always describes the combinatorics of a bounded polytope: this is any polytope which is projectively equivalent to the polyhedron defined by ''​VERTICES''​ or ''​POINTS''​ or dually modulo its ''​LINEALITY_SPACE''​. + - + - Each property must clearly specify if it depends on the geometry or only on the combinatorics. + - + - ==== Special Cases ==== + - + - Most of what comes below is a consequence of the design decisions explained above. + - + - === Empty polytopes === + - + - With the introduction of the ''​Cone''​ class and redefining ''​Polytope''​ as a derived class (in version 2.9.10) this raises the question of how to deal with empty polytopes. + - This is a bit subtle as the cone over an empty polytope does not have a canonical definition. ​ Most text books hence exclude this case.  For them a polytope is never empty. ​ There was a time when this was also polymake'​s point of view (until version 2.3). + - + - However, this was changed for the reason that often people generate systems of inequalities and then look at the feasible region. ​ Most of the time they obtain a polytope and proceed, but sometimes it fails, and the region is empty. ​ It is therefore necessary to give a definition of the empty polytope (geometrically) which is consistent:​ + - + - An empty polytope is recognized by ''​FEASIBLE == false''​. ​ Such a polytope is required to have ''​VERTICES''​ and ''​FACETS''​ empty. + - + - polytope > $e = new Polytope(POINTS=>​[]);​ + - polytope > print$e->​FEASIBLE;​ + - + - polytope > print $e->​FACETS;​ + - + - ​ + - This is totally different from having ''​VERTICES''​ or ''​FACETS''​ undefined (see above). + - <​code>​ + - polytope >$nc = new Polytope(VERTICES_IN_FACETS => cube(2)->​VERTICES_IN_FACETS);​ + - ​polytope > print $nc->​FACETS;​ + - polymake: ​WARNING: available properties insufficient to compute '​FACETS'​ + - ​ + - === Zero-dimensional polytopes === + - + - A zero-dimensional polytope is a single point. ​ In our model it has one vertex and one facet (the far hyperplane). + - <​code>​ + - polytope >$z = new Polytope(POINTS=>​[[1,​2,​3]]);​ + - + - polytope > print $z->​FACETS;​ + - 1 0 0 + - ​ + - + - ''​VERTICES_IN_FACETS''​ is a 1-by-1 matrix with a zero entry. ​ This means that the single vertex does //not// lie on the single facet. + - <​code>​ + - polytope > print$z->​VERTICES_IN_FACETS;​ + - {} + - ​ + - + - Such a polytope is both simple and simplicial, i.e. it is a simplex. + - <​code>​ + - polytope > print $z->​SIMPLICIAL,",",​$z->​SIMPLE;​ + - 1,1 + - ​ + - + - === Zero-dimensional fans === + - + - A zero-dimensional fan can e.g. be defined via + - <​code>​ + - polytope > \$f = new fan::​PolyhedralFan(RAYS=>​[],​ MAXIMAL_CONES=>​[[]]);​ + - ​ + - ==== Summing Up ==== + - For instance we have four possibilities which can occur for ''​VERTICES''​. The property + - * does not exist (it is not listed in ''​properties''​):​ This basically means that the property is not derived/​calculated,​ yet. + - * exists and is set to ''​undef'':​ Polymake is not able to derive this property with the given properties. The polytope may be empty or not. + - * exists and is empty: So the polytope is empty. + - * exists and is neither set to ''​undef''​ nor is empty: Our polytope is not empty and the property returns what you expect. +
• user_guide/tutorials/polytope_semantics.txt
• Last modified: 2019/02/04 22:55
• (external edit)