Basic facts about polyhedra

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.