<p>We know that every convex polyhedron has two representations, one as the intersection of finite halfspaces and the other as Minkowski sum of the convex hull of finite points and the nonnegative hull of finite directions. These are called <span class="SimpleMath">\(H\)</span>-representation and <span class="SimpleMath">\(V\)</span>-representation, respectively. CddInterface is a gap interface to the C package <code class="code">cddlib</code> which among other things can translate between these two representations.</p>
<h4>1.2 <span class="Heading">H-representation and V-representation of polyhedra</span></h4>
<p>Let us start by introducing the <span class="SimpleMath">\(H\)</span>-representation. Let <var class="Arg">A</var> be <var class="Arg">m x d</var> matrix and let <var class="Arg">b</var> be a column <var class="Arg">m</var>-vector. The <span class="SimpleMath">\(H\)</span>-representation of the polyhedron defined by the system <code class="code">b+Ax >= 0</code> of <var class="Arg">m</var> inequalities and <var class="Arg">d</var> variables <var class="Arg">x= (x_1,...,x_d)</var> is as follows:</p>
<div class="example"><pre>
H-representation
linearity t, [i_1, i_2, ...,i_t]
begin
m x (d+1) numbertype
b A
end
</pre></div>
<p>The linearity line is added when we want to specify that some rows of the system <span class="SimpleMath">\(b+Ax\)</span> are equalities. That is, <span class="SimpleMath">\(k\in \{i_1, i_2, \dots,i_t\}\)</span> means that the row <span class="SimpleMath">\(k\)</span> of the system <span class="SimpleMath">\(b+Ax\)</span> is specified to be equality.</p>
<p>For example, the <span class="SimpleMath">\(H\)</span>-representation of the polyhedron defined by the following system:</p>
<div class="example"><pre>
H-representation
linearity 2, [1, 3]
begin
3 x 5 rational
4 -3 6 0 -5
1 2 -2 -7 0
0 0 -3 0 5
end
</pre></div>
<p>Next we define Polyhedra <span class="SimpleMath">\(V\)</span>-format. Let <var class="Arg">P</var> be represented by <var class="Arg">n</var> gerating points and <var class="Arg">s</var> generating directions (rays) as</p>
<p>Then the Polyhedra <span class="SimpleMath">\(V\)</span>-format is for <var class="Arg">P</var> is:</p>
<div class="example"><pre>
V-representation
linearity t, [i_1, i_2,...,i_t]
begin
(n+s) x (d+1) numbertype
1 v_1
: :
1 v_n
0 r_{n+1}
: :
0 r_{n+s}
end
</pre></div>
<p>In the above format the generating points and generating rays may appear mixed in arbitrary order. Linearity for <span class="SimpleMath">\(V\)</span>-representation specifies a subset of generators whose coefficients are relaxed to be free. That is, <span class="SimpleMath">\(k \in \{i_1 , i_2 , . . . , i_t \}\)</span> specifies that the <span class="SimpleMath">\(k\)</span>-th generator is specified to be free. This means for each such a ray <span class="SimpleMath">\(r_k\)</span> , the line generated by <span class="SimpleMath">\(r_k\)</span> is in the polyhedron, and for each such a vertex <span class="SimpleMath">\(v_k\)</span> , its coefficient is no longer nonnegative but still the coefficients for all <span class="SimpleMath">\(v_i\)</span>’s must sum up to one.</p>
<p>For example the <span class="SimpleMath">\(V\)</span>-representation of the polyhedron defined as</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
