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 = P
o1 : Polyhedron
|
i2 : (C,L,M) = minkSummandCone P
o2 = (C, HashTable{0 => Polyhedron{...1...}}, | 1 0 |)
1 => Polyhedron{...1...} | 0 1 |
2 => Polyhedron{...1...} | 1 0 |
3 => Polyhedron{...1...} | 1 0 |
4 => Polyhedron{...1...} | 0 1 |
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
|