<?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>intersection -- computes the intersection of half-spaces, hyperplanes, cones, and polyhedra</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_is__Compact.html">next</a> | <a href="_interior__Vector.html">previous</a> | <a href="_is__Compact.html">forward</a> | <a href="_interior__Vector.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>intersection -- computes the intersection of half-spaces, hyperplanes, cones, 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 = intersection L </tt><br/><tt>C = intersection M </tt><br/><tt>C = intersection(M,N) </tt><br/><tt>P = intersection(M,v) </tt><br/><tt>P = intersection(M,v,N,w) </tt><br/><tt>C = intersection(C1,C2) </tt><br/><tt>P = intersection(P1,P2)</tt></div>
</dd></dl>
</div>
</li>
<li><div class="single">Inputs:<ul><li><span><tt>L</tt>, <span>a <a href="../../Macaulay2Doc/html/___List.html">list</a></span>, containing any of the inputs below</span></li>
<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>v</tt>, <span>a <a href="../../Macaulay2Doc/html/___Matrix.html">matrix</a></span>, with only one column and 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>w</tt>, <span>a <a href="../../Macaulay2Doc/html/___Matrix.html">matrix</a></span>, with only one column and 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>C1</tt>, <span>a <a href="___Cone.html">convex rational cone</a></span></span></li>
<li><span><tt>C2</tt>, <span>a <a href="___Cone.html">convex rational cone</a></span></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>
</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>
<li><span><tt>C</tt>, <span>a <a href="___Cone.html">convex rational cone</a></span></span></li>
</ul>
</div>
</li>
</ul>
</div>
<div class="single"><h2>Description</h2>
<div><p/>
When inserting any of the combination of matrices into <tt>intersection</tt>, it considers the given matrices as defining
inequalities and equalities. Thus, it either computes the polyhedron <tt>P = {p | M*p <= v and N*p = w }</tt>. Therefore, <tt>M</tt> and <tt>N</tt> must have the same number of columns, which will be the
dimension of the ambient space, and <tt>M</tt> and <tt>v</tt> as
well as <tt>N</tt> and <tt>w</tt> must have the same number of
rows respectively. If <tt>N</tt> and <tt>w</tt> are omitted then
the polyhedron is just given by the inequalities. If <tt>v</tt>
and <tt>w</tt> are omitted then they are considered to be 0 so
that the intersection is a cone and thus the output is of class Cone.<p/>
If two polyhedra or two cones are inserted, then the
intersection of both arguments is computed if both arguments lie in
the same ambient space. If both arguments are cones then the output
is again a cone. Otherwise intersection returns a polyhedron.<p/>
If <tt>intersection</tt> is called for a list <tt>L</tt>,
then the list may contain a combination of the following in any order.<ul><li>Inequalities, given by a sequence <tt>(M,v)</tt> of 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> determining inequalities as above</li>
<li>Equalities, given by a list <tt>{N,w}</tt> of 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> determining equalities as above</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>intersection</tt> computes the intersection 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/>
The first use of <tt>intersection</tt> is to construct a cone:<table class="examples"><tr><td><pre>i1 : M = matrix {{1,2,3},{2,3,1},{3,1,2}}
o1 = | 1 2 3 |
| 2 3 1 |
| 3 1 2 |
3 3
o1 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i2 : C = intersection M
o2 = {ambient dimension => 3 }
dimension of lineality space => 0
dimension of the cone => 3
number of facets => 3
number of rays => 3
o2 : Cone</pre>
</td></tr>
</table>
<p/>
This is the cone of all points that are positive on the rows of the
matrix <tt>M</tt>. If we add another row to this matrix and enter a condition
vector we get a polyhedron:<table class="examples"><tr><td><pre>i3 : M = M || matrix {{-1,-1,-1}}
o3 = | 1 2 3 |
| 2 3 1 |
| 3 1 2 |
| -1 -1 -1 |
4 3
o3 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i4 : v = matrix {{1},{2},{3},{4}}
o4 = | 1 |
| 2 |
| 3 |
| 4 |
4 1
o4 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i5 : P = intersection(M,v)
o5 = {ambient dimension => 3 }
dimension of lineality space => 0
dimension of polyhedron => 3
number of facets => 4
number of rays => 0
number of vertices => 4
o5 : Polyhedron</pre>
</td></tr>
</table>
<p/>
This polyhedron, a tetrahedron, consists of all points <tt>p</tt> such
that <tt>M*p <= v</tt>. If add a another pair of matrices, these conditions are
evaluated as equalities. Thus we get a polyhedron which is not of full dimension.
It is an intersection with an affine hyperplane.<table class="examples"><tr><td><pre>i6 : N = matrix {{1,2,0}}
o6 = | 1 2 0 |
1 3
o6 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i7 : w = matrix {{2}}
o7 = | 2 |
1 1
o7 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i8 : Q = intersection (M,v,N,w)
o8 = {ambient dimension => 3 }
dimension of lineality space => 0
dimension of polyhedron => 2
number of facets => 4
number of rays => 0
number of vertices => 4
o8 : Polyhedron</pre>
</td></tr>
</table>
<p/>
If we have another polyehdron or cone, we can also intersect them with the others.<table class="examples"><tr><td><pre>i9 : HC = intersection(matrix {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}},matrix {{1},{1},{1},{1},{1},{1}})
o9 = {ambient dimension => 3 }
dimension of lineality space => 0
dimension of polyhedron => 3
number of facets => 6
number of rays => 0
number of vertices => 8
o9 : Polyhedron</pre>
</td></tr>
<tr><td><pre>i10 : C1 = intersection(C,HC)
o10 = {ambient dimension => 3 }
dimension of lineality space => 0
dimension of polyhedron => 3
number of facets => 6
number of rays => 0
number of vertices => 8
o10 : Polyhedron</pre>
</td></tr>
<tr><td><pre>i11 : Q1 = intersection(P,HC)
o11 = {ambient dimension => 3 }
dimension of lineality space => 0
dimension of polyhedron => 3
number of facets => 9
number of rays => 0
number of vertices => 13
o11 : Polyhedron</pre>
</td></tr>
</table>
</div>
</div>
<div class="waystouse"><h2>Ways to use <tt>intersection</tt> :</h2>
<ul><li>intersection(Cone,Cone)</li>
<li>intersection(Cone,Polyhedron)</li>
<li>intersection(List)</li>
<li>intersection(Matrix)</li>
<li>intersection(Matrix,Matrix)</li>
<li>intersection(Matrix,Matrix,Matrix,Matrix)</li>
<li>intersection(Polyhedron,Cone)</li>
<li>intersection(Polyhedron,Polyhedron)</li>
</ul>
</div>
</div>
</body>
</html>
