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 QQ <--- QQ
|
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
|