Quelle  chap2.html   Sprache: HTML

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (CddInterface) - Chapter 2: Creating polyhedra and their Operations</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap2"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2_mj.html">[MathJax on]</a></p>
<p><a id="X7CA75753797126E1" name="X7CA75753797126E1"></a></p>
<div class="ChapSects"><a href="chap2.html#X7CA75753797126E1">2 <span class="Heading">Creating polyhedra and their Operations</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X84D9DB317A23B6C9">2.1 <span class="Heading">Creating a polyhedron</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7AB5A29C82FEBC24">2.1-1 Cdd_PolyhedronByInequalities</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7DF57D1586FEFAA8">2.1-2 Cdd_PolyhedronByGenerators</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X876837A483D59A93">2.2 <span class="Heading">Some operations on a polyhedron</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X81941B158503C052">2.2-1 Cdd_FourierProjection</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X80CE410083662BB8">2.3 <span class="Heading">Some operations on two polyhedrons</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X811F5CBB8096383B">2.3-1 Cdd_IsContained</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X82E1352D7A0DCA38">2.3-2 Cdd_Intersection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X86E9928D806EADA6"><code>2.3-3 \+</code></a></span>
</div></div>
</div>

<h3>2 <span class="Heading">Creating polyhedra and their Operations</span></h3>

<p><a id="X84D9DB317A23B6C9" name="X84D9DB317A23B6C9"></a></p>

<h4>2.1 <span class="Heading">Creating a polyhedron</span></h4>

<p><a id="X7AB5A29C82FEBC24" name="X7AB5A29C82FEBC24"></a></p>

<h5>2.1-1 Cdd_PolyhedronByInequalities</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Cdd_PolyhedronByInequalities</code>( <var class="Arg">ineq</var>[, <var class="Arg">linearities_list</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a CddPolyhedron</p>

<p>The function takes a list in which every entry represents an inequality (or equality). In case we want some entries to represent equalities we should refer in a second list to their indices.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:= Cdd_PolyhedronByInequalities( [ [ 0, 1, 0 ], [ 0, 1, -1 ] ] );</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( A );</span>
H-representation
begin
   2 X 3  rational

   0   1   0
   0   1  -1
end
<span class="GAPprompt">gap></span> <span class="GAPinput">B:= Cdd_PolyhedronByInequalities( [ [ 0, 1, 0 ], [ 0, 1, -1 ] ], [ 2 ] );</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( B );</span>
H-representation
linearity 1, [ 2 ]
begin
   2 X 3  rational

   0   1   0
   0   1  -1
end
</pre></div>

<p><a id="X7DF57D1586FEFAA8" name="X7DF57D1586FEFAA8"></a></p>

<h5>2.1-2 Cdd_PolyhedronByGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Cdd_PolyhedronByGenerators</code>( <var class="Arg">genes</var>[, <var class="Arg">linearities_list</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a CddPolyhedron</p>

<p>The function takes a list in which every entry represents a vertex in the ambient vector space. In case we want some vertices to be free (the vertex and its negative belong to the polyhedron) we should refer in a second list to their indices .</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A:= Cdd_PolyhedronByGenerators( [ [ 0, 1, 3 ], [ 1, 4, 5 ] ] );</span>
<Polyhedron given by its V-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( A );</span>
V-representation
begin
   2 X 3  rational

   0  1  3
   1  4  5
end
<span class="GAPprompt">gap></span> <span class="GAPinput">B:= Cdd_PolyhedronByGenerators( [ [ 0, 1, 3 ] ], [ 1 ] );</span>
<Polyhedron given by its V-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( B );</span>
V-representation
linearity 1, [ 1 ]
begin
   1 X 3  rational

   0  1  3
end
</pre></div>

<p><a id="X876837A483D59A93" name="X876837A483D59A93"></a></p>

<h4>2.2 <span class="Heading">Some operations on a polyhedron</span></h4>

<p><a id="X81941B158503C052" name="X81941B158503C052"></a></p>

<h5>2.2-1 Cdd_FourierProjection</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Cdd_FourierProjection</code>( <var class="Arg">P</var>, <var class="Arg">i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a CddPolyhedron</p>

<p>The function returns the Fourier projection of the polyhedron in the subspace <span class="Math">(O,x_1,\dots,x_{i-1},x_{i+1},\dots,x_n)</span> after applying the Fourier elemination algorithm to get rid of the variable <span class="Math">x_{i}</span>.</p>

<p>To illustrate this projection, Let <span class="Math">P= \mathrm{conv}( (1,2), (4,5) )</span> in <span class="Math">\mathbb{Q}^2</span>. <span class="Math">\newline</span> To find its projection on the subspace <span class="Math">(O, x_1)</span>, we apply the Fourier elemination to get rid of <span class="Math">x_2</span></p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := Cdd_PolyhedronByGenerators( [ [ 1, 1, 2 ], [ 1, 4, 5 ] ] );</span>
<Polyhedron given by its V-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">H := Cdd_H_Rep( P );</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( H );</span>
H-representation
linearity 1, [ 3 ]
begin
   3 X 3  rational

    4  -1   0 
   -1   1   0 
   -1  -1   1 
end
<span class="GAPprompt">gap></span> <span class="GAPinput">P_x1 := Cdd_FourierProjection( H, 2);</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( P_x1 );</span>
H-representation
linearity 1, [ 3 ]
begin
   3 X 3  rational

    4  -1   0
   -1   1   0
    0   0   1
end
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( P_x1 ) );</span>
V-representation
begin
   2 X 3  rational

   1  1  0
   1  4  0
end
</pre></div>

<p>Let again <span class="Math">Q= Conv( (2,3,4), (2,4,5) )+ nonneg( (1,1,1) )</span>, and let us compute its projection on <span class="Math">(O,x_2,x_3)</span></p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Q := Cdd_PolyhedronByGenerators( [ [ 1, 2, 3, 4 ],[ 1, 2, 4, 5 ], [ 0, 1, 1, 1 ] ] );</span>
<Polyhedron given by its V-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := Cdd_H_Rep( Q );</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( R );</span>
H-representation
linearity 1, [ 4 ]
begin
   4 X 4  rational

    2   1  -1   0 
   -2   1   0   0 
   -1  -1   1   0 
   -1   0  -1   1 
end
<span class="GAPprompt">gap></span> <span class="GAPinput">P_x2_x3 := Cdd_FourierProjection( R, 1);</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( P_x2_x3 );</span>
H-representation
linearity 2, [ 1, 3 ]
begin
   3 X 4  rational

   -1   0  -1   1 
   -3   0   1   0 
    0   1   0   0 
end
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( last ) ) ;</span>
V-representation 
begin
   2 X 4  rational
               
   0  0  1  1 
   1  0  3  4 
end
</pre></div>

<p><a id="X80CE410083662BB8" name="X80CE410083662BB8"></a></p>

<h4>2.3 <span class="Heading">Some operations on two polyhedrons</span></h4>

<p><a id="X811F5CBB8096383B" name="X811F5CBB8096383B"></a></p>

<h5>2.3-1 Cdd_IsContained</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Cdd_IsContained</code>( <var class="Arg">P1</var>, <var class="Arg">P2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="code">true</code> or <code class="code">false</code></p>

<p>The function returns <code class="code">true</code> if <span class="Math">P_1</span> is contained in <span class="Math">P_2</span>, otherwise returns <code class="code">false</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := Cdd_PolyhedronByInequalities( [ [ 10, -1, 1, 0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ -24, 9, 2, 0 ], [ 1, 1, -1, 0 ], [ -23, -12, 1, 11 ] ], [ 4 ] );</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">B := Cdd_PolyhedronByInequalities( [ [ 1, 0, 0, 0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ -4, 1, 0, 0 ], [ 10, -1, 1, 0 ], [ -3, -1, 0, 1 ] ], [ 3, 4 ] );</span>
<Polyhedron given by its H-representation>
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_IsContained( B, A );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( A ) );</span>
V-representation
begin
   3 X 4  rational

   1   2   3   4
   1   4  -6   7
   0   1   1   1
end
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( B ) );</span>
V-representation
begin
   2 X 4  rational

   1   4  -6   7
   0   1   1   1
end
</pre></div>

<p><a id="X82E1352D7A0DCA38" name="X82E1352D7A0DCA38"></a></p>

<h5>2.3-2 Cdd_Intersection</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; Cdd_Intersection</code>( <var class="Arg">P1</var>, <var class="Arg">P2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a CddPolyhedron</p>

<p>The function returns the intersection of <span class="Math">P_1</span> and <span class="Math">P_2</span></p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">A := Cdd_PolyhedronByInequalities( [ [ 3, 4, 5 ] ], [ 1 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">B := Cdd_PolyhedronByInequalities( [ [ 9, 7, 2 ] ], [ 1 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">C := Cdd_Intersection( A, B );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( A ) );</span>
V-representation
linearity 1, [ 2 ]
begin
   2 X 3  rational

   1  -3/4     0
   0    -5     4
end
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( B ) );</span>
V-representation
linearity 1, [ 2 ]
begin
   2 X 3  rational

   1  -9/7     0
   0    -2     7
end
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( Cdd_V_Rep( C ) );</span>
V-representation
begin
   1 X 3  rational

   1  -13/9    5/9
end
</pre></div>

<p><a id="X86E9928D806EADA6" name="X86E9928D806EADA6"></a></p>

<h5><code>2.3-3 \+</code></h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; \+</code>( <var class="Arg">P1</var>, <var class="Arg">P2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a CddPolyhedron</p>

<p>The function returns the Minkuwski sum of <span class="Math">P_1</span> and <span class="Math">P_2</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := Cdd_PolyhedronByGenerators( [ [ 1, 2, 5 ], [ 0, 1, 2 ] ] );</span>
< Polyhedron given by its V-representation >
<span class="GAPprompt">gap></span> <span class="GAPinput">Q := Cdd_PolyhedronByGenerators( [ [ 1, 4, 6 ], [ 1, 3, 7 ], [ 0, 3, 1 ] ] );</span>
< Polyhedron given by its V-representation >
<span class="GAPprompt">gap></span> <span class="GAPinput">S := P+Q;</span>
< Polyhedron given by its H-representation >
<span class="GAPprompt">gap></span> <span class="GAPinput">V := Cdd_V_Rep( S );</span>
< Polyhedron given by its V-representation >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( V );</span>
V-representation 
begin
   4 X 3  rational

   0   3   1 
   1   6  11 
   1   5  12 
   0   1   2 
end
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_GeneratingVertices( P ); </span>
[ [ 2, 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_GeneratingVertices( Q );</span>
[ [ 3, 7 ], [ 4, 6 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_GeneratingVertices( S );</span>
[ [ 5, 12 ], [ 6, 11 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_GeneratingRays( P );</span>
[ [ 1, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_GeneratingRays( Q );</span>
[ [ 3, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Cdd_GeneratingRays( S );</span>
[ [ 1, 2 ], [ 3, 1 ] ]
</pre></div>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>