minkSummandCone -- computes the Cone of all Minkowski summands and the minimal decompositions

Synopsis

• Usage:
(C,L,M) = minkSummandCone P
• Inputs:
• Outputs:
• L, a list, containing Polyhedra
• M,

Description

For the Minkowski summand cone one takes QQ^d where d is the number of edges of the input polyhedron P. Every Minkowski summand of P has only edges that are edges of P, so it can be constructed by rescaling every edge of P, i.e. is represented by a point in QQ^d. But not every point in QQ^d gives a polyhedron via this method. This is the case if on the one hand the point lies in the positive orthant and on the other hand for every compact two dimensional face of P the rescaled edges of such a face give a two dimensional polytope, i.e. the sum of the ordered rescaled edge directions is zero. Therefore, every compact two dimensional face of P gives a set of linear equalities on a part of the variables in QQ^d. The Minkowski Summand Cone C is the intersection of the positive orthant with these equations. Thus, every point in C corresponds to a Minkowski summand (probably after rescaling). The corresponding polyhedron to every minimal generator of C is saved in the hash table L. Finally, all possible minimal decompositions of P are saved as columns in the matrix M.

For example, consider the Minkowski summand cone of the hexagon.

 i1 : P = convexHull matrix{{2,1,-1,-2,-1,1},{0,1,1,0,-1,-1}} o1 = {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 6 number of rays => 0 number of vertices => 6 o1 : Polyhedron i2 : (C,L,M) = minkSummandCone P o2 = ({ambient dimension => 6 }, HashTable{0 => dimension of lineality space => 0 dimension of the cone => 4 number of facets => 6 number of rays => 5 1 => 2 => 3 => 4 => ------------------------------------------------------------------------ {ambient dimension => 2 }}, | 1 0 |) dimension of lineality space => 0 | 0 1 | dimension of polyhedron => 1 | 1 0 | number of facets => 2 | 1 0 | number of rays => 0 | 0 1 | number of vertices => 2 {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 3 number of rays => 0 number of vertices => 3 {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 1 number of facets => 2 number of rays => 0 number of vertices => 2 {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 1 number of facets => 2 number of rays => 0 number of vertices => 2 {ambient dimension => 2 } dimension of lineality space => 0 dimension of polyhedron => 2 number of facets => 3 number of rays => 0 number of vertices => 3 o2 : Sequence

Thus, we see that the minimal Minkowski summands of the hexagon are two triangles and three lines and that there are two minimal decompositions, i.e. the hexagon is the sum of the two triangles or the three lines:

 i3 : rays C o3 = | 1 0 0 0 1 | | 0 1 0 1 0 | | 0 1 1 0 0 | | 1 1 0 0 0 | | 0 0 1 0 1 | | 0 0 0 1 1 | 6 5 o3 : Matrix ZZ <--- ZZ i4 : apply(values L,vertices) o4 = {| 0 2 |, | 0 2 1 |, | 0 1 |, | 0 1 |, | 0 2 1 |} | 0 0 | | 0 0 -1 | | 0 1 | | 0 -1 | | 0 0 1 | o4 : List i5 : M o5 = | 1 0 | | 0 1 | | 1 0 | | 1 0 | | 0 1 | 5 2 o5 : Matrix QQ <--- QQ

Ways to use minkSummandCone :

• "minkSummandCone(Polyhedron)"

For the programmer

The object minkSummandCone is .