<?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>convexHull -- computing the convex hull of points, rays and polyhedra</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_cross__Polytope.html">next</a> | <a href="_contains.html">previous</a> | <a href="_cross__Polytope.html">forward</a> | <a href="_contains.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>convexHull -- computing the convex hull of points, rays and polyhedra</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> P = convexHull M </tt><br/><tt>P = convexHull(M,N) </tt><br/><tt>P = convexHull(P1,P2) </tt><br/><tt>P = convexHull L</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>M</tt>, <span>a <a href="../../Macaulay2Doc/html/___Matrix.html">matrix</a></span>, with entries in<a href="../../Macaulay2Doc/html/___Z__Z.html" title="the class of all integers">ZZ</a> or <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a></span></li>
<li><span><tt>N</tt>, <span>a <a href="../../Macaulay2Doc/html/___Matrix.html">matrix</a></span>, with entries in<a href="../../Macaulay2Doc/html/___Z__Z.html" title="the class of all integers">ZZ</a> or <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a></span></li>
<li><span><tt>P1</tt>, <span>a <a href="___Polyhedron.html">convex polyhedron</a></span></span></li>
<li><span><tt>P2</tt>, <span>a <a href="___Polyhedron.html">convex polyhedron</a></span></span></li>
<li><span><tt>L</tt>, <span>a <a href="../../Macaulay2Doc/html/___List.html">list</a></span></span></li>
</ul>
</div>
</li>
<li><div class="single">Outputs:<ul><li><span><tt>P</tt>, <span>a <a href="___Polyhedron.html">convex polyhedron</a></span></span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div><p/>
<tt>convexHull</tt> computes the convex hull of the input.
In the first two cases it considers the columns of <tt>M</tt>
as a set of points and the columns of <tt>N</tt> (if given) as
a set of rays and computes the polyhedron that is the convex hull
of the points plus the rays. The two matrices must have the same
number of rows, i.e. the columns must lie in the same ambient space.
If <tt>N</tt> is not given or equal to 0, then the resulting
polyhedron is compact and hence a polytope. The points need not
be the vertices of the polyhedron. In the third case it computes
the convex hull of <tt>P1</tt> and <tt>P2</tt> if they lie
in the same ambient space. Finally, it computes the convex hull
of a list <tt>L</tt> where the list may contain a combination
of the following in any order.<ul><li>Vertices, given by a matrix <tt>M</tt> over <a href="../../Macaulay2Doc/html/___Z__Z.html" title="the class of all integers">ZZ</a>
or <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a></li>
<li>Vertices and rays, given by a sequence <tt>(V,R)</tt>of two
matrices over <a href="../../Macaulay2Doc/html/___Z__Z.html" title="the class of all integers">ZZ</a> or <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a></li>
<li><a href="___Cone.html" title="the class of all rational convex polyhedral cones">Cone</a></li>
<li><a href="___Polyhedron.html" title="the class of all convex polyhedra">Polyhedron</a></li>
</ul>
<p/>
Then <tt>convexHull</tt> computes the convex hull of all
inserted objects, if they are in the same ambient space, i.e. all matrices
must have the same number of rows, which must equal the ambient dimension
of all cones and polyhedra.<p/>
For example, consider the square in <a href="../../Macaulay2Doc/html/___Q__Q.html" title="the class of all rational numbers">QQ</a>^2:<table class="examples"><tr><td><pre>i1 : M = matrix {{1,1,-1,-1},{1,-1,1,-1}}
o1 = | 1 1 -1 -1 |
| 1 -1 1 -1 |
2 4
o1 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i2 : P = convexHull M
o2 = {ambient dimension => 2 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 4
number of rays => 0
number of vertices => 4
o2 : Polyhedron</pre>
</td></tr>
</table>
<p/>
If we add a ray, then it is not compact anymore:<table class="examples"><tr><td><pre>i3 : r = matrix {{1},{2}}
o3 = | 1 |
| 2 |
2 1
o3 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i4 : P =convexHull(M,r)
o4 = {ambient dimension => 2 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 4
number of rays => 1
number of vertices => 3
o4 : Polyhedron</pre>
</td></tr>
</table>
<p/>
If we add some more vertices to <tt>M</tt> then we get a hexagon:<table class="examples"><tr><td><pre>i5 : N = matrix {{-2,-2,0},{0,-2,-2}}
o5 = | -2 -2 0 |
| 0 -2 -2 |
2 3
o5 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i6 : Q = convexHull(M|N)
o6 = {ambient dimension => 2 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 6
number of rays => 0
number of vertices => 6
o6 : Polyhedron</pre>
</td></tr>
</table>
<p/>
Again if we add the ray <tt>r</tt> then the polyhedron is not compact:<table class="examples"><tr><td><pre>i7 : Q1 = convexHull(M|N,r)
o7 = {ambient dimension => 2 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 5
number of rays => 1
number of vertices => 4
o7 : Polyhedron</pre>
</td></tr>
</table>
<p/>
To get this polyhedron we could also have used the application of <tt>convexHull</tt>
to lists or pairs of polyhedra:<table class="examples"><tr><td><pre>i8 : P1 = convexHull {P,N}
o8 = {ambient dimension => 2 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 5
number of rays => 1
number of vertices => 4
o8 : Polyhedron</pre>
</td></tr>
<tr><td><pre>i9 : P1 == Q1
o9 = true</pre>
</td></tr>
<tr><td><pre>i10 : P1 = convexHull(P,Q)
o10 = {ambient dimension => 2 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 5
number of rays => 1
number of vertices => 4
o10 : Polyhedron</pre>
</td></tr>
<tr><td><pre>i11 : P1 == Q1
o11 = true</pre>
</td></tr>
</table>
</div>
</div>
<div class="waystouse"><h2>Ways to use <tt>convexHull</tt> :</h2>
<ul><li>convexHull(List)</li>
<li>convexHull(Matrix)</li>
<li>convexHull(Matrix,Matrix)</li>
<li>convexHull(Polyhedron,Polyhedron)</li>
</ul>
</div>
</div>
</body>
</html>
