Quelle intro.autodoc Sprache: unbekannt

@Chapter Introduction
@Section Why CddInterface
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 $H$-representation and $V$-representation,
respectively. CddInterface is a gap interface to the C package <C>cddlib</C> which among other things can translate
between these two representations.
@Section H-representation and V-representation of polyhedra

Let us start by introducing the $H$-representation. Let <A>A</A> be <A>m x d</A> matrix and let <A>b</A> be a column <A>m</A>-vector.
The $H$-representation of the polyhedron defined by the system
<C>b+Ax >= 0</C> of <A>m</A> inequalities and <A>d</A> variables <A>x= (x_1,...,x_d)</A> is as follows:

@BeginCode Increment
H-representation
linearity t, [i_1, i_2, ...,i_t]
begin
  m x (d+1) numbertype
  b  A
end
@EndCode
@InsertCode Increment

The linearity line is added when we want to specify that some rows of the system $b+Ax$ are equalities.
That is, $k\in \{i_1, i_2, \dots,i_t\}$ means that the row $k$ of the system $b+Ax$ is specified to be equality.

For example, the $H$-representation of the polyhedron defined by the following system:

$4-3x_1+6x_2-5x_4 = 0, 1+2x_1-2x_2-7x_3 \geq 0, -3x_2+5x_4 = 0;$

is the following:

@BeginCode Increment2
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
@EndCode
@InsertCode Increment2

Next we define Polyhedra $V$-format. Let <A>P</A> be represented by <A>n</A> gerating points and <A>s</A> generating
directions (rays) as $$P = \mathrm{conv}(v_1 , \dots , v_n ) + \mathrm{nonneg}(r_{n+1} , \dots , r_{n+s} ).$$
Then the Polyhedra $V$-format is for <A>P</A> is:

@BeginCode Increment3
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
@EndCode
@InsertCode Increment3

In the above format the generating points and generating rays may appear mixed in arbitrary order.
Linearity for $V$-representation specifies a subset of generators whose coefficients are relaxed to
be free. That is, $k \in \{i_1 , i_2 , . . . , i_t \}$ specifies that the $k$-th generator is specified to be free.
This means for each such a ray $r_k$ , the line generated by $r_k$ is in the polyhedron,
and for each such a vertex $v_k$ , its coefficient is no longer nonnegative but still the coefficients for all
$v_i$’s must sum up to one.

For example the $V$-representation of the polyhedron defined as
$$P:= \mathrm{conv}( (2,3), (-2,-3), (-1,2) ) + \mathrm{nonneg}(\; (1,2) , (-1,-2), (1,1)\;)$$

@BeginCode Increment4
V-representation
linearity 2, [ 1, 3 ]
begin
4 x 3 rational
1   2   3
1  -1   2
0   1   2
0   1   1
end
@EndCode
@InsertCode Increment4

Quelle intro.autodoc Sprache: unbekannt

[ Dauer der Verarbeitung: 0.11 Sekunden (vorverarbeitet) ]