<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>minkSummandCone -- computes the Cone of all Minkowski summands and the minimal decompositions</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_net_lp__Cone_rp.html">next</a> | <a href="_minkowski__Sum.html">previous</a> | <a href="_net_lp__Cone_rp.html">forward</a> | <a href="_minkowski__Sum.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<hr/>
<div><h1>minkSummandCone -- computes the Cone of all Minkowski summands and the minimal decompositions</h1>
<div class="single"><h2>Synopsis</h2>
<ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt> (C,L,M) = minkSummandCone P</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>P</tt>, <span>a <a href="___Polyhedron.html">convex polyhedron</a></span></span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span><tt>C</tt>, <span>a <a href="___Cone.html">convex rational cone</a></span></span></li>
<li><span><tt>L</tt>, <span>a <a href="../../Macaulay2Doc/html/___List.html">list</a></span>, containing Polyhedra</span></li>
<li><span><tt>M</tt>, <span>a <a href="../../Macaulay2Doc/html/___Matrix.html">matrix</a></span></span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div><p/>
For the Minkowski summand cone one takes <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a>^d where d is the number
of edges of the input polyhedron <tt>P</tt>. Every Minkowski summand of <tt>P</tt> has
only edges that are edges of <tt>P</tt>, so it can be constructed by rescaling every
edge of <tt>P</tt>, i.e. is represented by a point in <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a>^d. But not every point
in <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a>^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 <tt>P</tt> 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 <tt>P</tt> gives a set of linear equalities on a part of
the variables in <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a>^d. The Minkowski Summand Cone <tt>C</tt> is the intersection
of the positive orthant with these equations. Thus, every point in <tt>C</tt> corresponds
to a Minkowski summand (probably after rescaling). The corresponding polyhedron to every
minimal generator of <tt>C</tt> is saved in the hash table <tt>L</tt>. Finally, all possible
minimal decompositions of <tt>P</tt> are saved as columns in the matrix <tt>M</tt>.<p/>
For example, consider the Minkowski summand cone of the hexagon.<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
<p/>
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:<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i5 : M
o5 = | 1 0 |
| 0 1 |
| 1 0 |
| 1 0 |
| 0 1 |
5 2
o5 : Matrix QQ <--- QQ</pre>
</td></tr>
</table>
</div>
</div>
<div class="waystouse"><h2>Ways to use <tt>minkSummandCone</tt> :</h2>
<ul><li>minkSummandCone(Polyhedron)</li>
</ul>
</div>
</div>
</body>
</html>
