[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

Convex polyhedra have two dual possible representations: you can define a polyhedron with by giving either a set of linear constraints or a set of generators:

*P={ x \in Q^d | A.x >= b }*

*P={ x \in Q^d | \forall i : A_i.x >= b_i }*

or

*P = { x \in Q^d | x = V.\lambda + R.\mu, \sum_i \lambda_i = 1, \mu >= 0 }*

*P = { x \in Q^d | x = \sum_i \lambda_i V_i + \sum_j \mu_j R_j }*

*A* is the constraints matrix, *V* the vertices matrix and
*R* the rays matrix. *x, b, \lambda, \mu* are column vectors.

Working in a linear framework instead of an affine one is much more
simpler, as a consequence we will embed *Q^d* in *Q^(d+1)* in
a classical way with the transformation *x ==> (\xi=1,x)*
with *\xi >= 0*, as explained for example in wilde93. Any
polyhedron will then be a cone. The reverse transformation is the
intersection of the cone with the hyperplane *\xi = 1*. This allows
us to concentrate our attention to cones, dual representations of which
are:

*P = { x \in Q^(d+1) | A.x >= 0 }*

*P = { x \in Q^(d+1) | x = R.\mu, \mu >= 0 }*
The double description method is a method to convert from one
representation to another and to minimize the size of representation.
This allows easily to perform intersection of convex polyhedra, by
merging the constraints of the involved polyhedra, or convex hull, by
merging generators of the involved polyhedra.

This document was generated on