Parameterized polyhedra representation

Polylib manipulates rational polyhedra as seen in the previous chapters. There are two dual representations of polyhedra: the implicit representation, as a set of constraints, and the Minkowski representation, as a set of lines, rays and vertices.

A parameterized polyhedron is defined in the implicit form by a finite number of inequalities and equalities, the difference from the classical approach being that the constant part depends linearly on a parameter vector $p$ for both equalities and inequalities:

$$D(p) = \{ x \in Q ^{n} \mid A x = A' p + a ,\quad B x \geq B' p + b \} \qquad\qquad \mbox{with } p \in Q^m$$

where $A$ is a $k \times n$ integer matrix, $A'$ a $k \times m$ integer matrix, $a$ is an integer $k$-vector, $B$ is a $k' \times n$ integer matrix, $B'$ a $k' \times m$ integer matrix and $b$ is an integer $k'$-vector.

The Minkowski representation, as a set of lines, rays, and vertices, of a parameterized polyhedron is:

$$D(p) = \left\{ x \in Q ^{n} \mid x = L \lambda + R \mu + V(... ...forall \mu \ge 0, ~ \forall \nu \ge 0,~ \sum \nu = 1 \right\}$$

where $L$ is the matrix containing the lines, $R$ the matrix containing the rays, and $V(p)$ the matrix depending on the parameters $p$ containing the vertices of the polyhedron.

Polylib includes an algorithm computing the vertices $V(p)$ of a parameterized polyhedron.