next up previous contents
Next: Main functions in Polyhedron.c Up: Polyhedra Previous: Polyhedra   Contents

Theoretical background

A nonempty set $C$ of points in a Euclidean space is called a (convex) cone if $\lambda x + \mu y\in C$ whenever $x,y\in
C$ and $\lambda ,\mu \geq 0$. A cone $C$ is polyhedral if

C=\{x \vert Ax\leq 0\}

for some matrix $A$, i.e. if $C$ is the intersection of finitely many linear half-spaces. Results from the linear programming theory [SCH86] shows that the concepts of polyhedral and finitely generated are equivalent.

Theorem 1   (Farkas-Minkowski-Weyl) A convex cone is polyhedral if and only if it is finitely generated.

A short definition of a polyhedra may be a finitely generated convex cone but in fact we are talking about the geometric representation of a list of constraints provided as a linear system of equations and inequalities.

Definition 1   (Polyhedron) A convex polyhedron if it is the set of solutions to a finite system of linear inequalities. It is called a convex polytope if it is a convex polyhedron and it is bounded. When a convex polyhedron (or polytope) has dimension $k$, it is called a $k$-polyhedron ($k$-polytope).

Hence, a set $P$ of vectors in $R^{n}$ is called a (convex) polyhedron if:

P=\{x\vert Ax\leq b\}

for some matrix $A$ and a vector $b$, i.e $P$ is the intersection of finitely many affine half-spaces. The concept of polyhedron and polytope are related by the means of the decomposition theorem for polyhedra.

Theorem 2   (Decomposition theorem for polyhedra) A set $P$ of vectors in a Euclidean space is a polyhedron, if and only if $P=Q+C$ for some polytope $Q$ and some polyhedral cone $C$.

For a set of vectors $a_{1},\cdots,a_{n}$, if a vector $b$ does not belong to the cone generated by these vectors, then there exists a hyperplane separating $b$ from from $a_{1},\cdots,a_{n}$. This result has also been formulated in the Farkas' lemma. A variant of this result is the following:

Lemma 1   Let $A$ be a matrix and let $b$ be a vector. Then the system $A x\leq
b$ of linear inequalities has a solution $x$, if and only of $y b\geq
0$ for each row vector $y \geq 0$ with $y A = 0$.

In Polylib the decomposition theorem is extensively used (in its extended form for polyhedra). A polyhedron $P$ can be represented by a set of inequalities (usually, implicit equalities are represented in a separate matrix): $P=\{x\vert Ax=b, Cx\geq d\}$, this representation is called implicit. From the Minkovski characterization, we know that $P$ has a dual representation, called the parametric representation.

P=\{x \vert x=L\lambda +R\mu +V\nu, \mu, \nu \geq 0, \sum \nu=1\}

Hence, each point of $P$ can be expressed as a sum of:

Although the polyhedra theory cannot be detailed here, we review a set of important concepts that are used when manipulating polyhedra. For a more precise description, please refer to [SCH86,Wil93].

Polylib implements procedures to compute, from one representation of a polyhedron $P$ (implicit of parametric), its dual representation of $P$, given the implicit on. The algorithms was proposed by Chernikova [Che65] which rediscovered the double description representation introduced by Motzkin. Important improvements were made in the conversion process between these representations by Fernandez [FQ88] and Le Verge [Le 92].

Based on this kernel algorithm, Polylib propose many computational function on polyhedra. More precisely, Polylib manipulates domains which are finite unions of polyhedra 3.1.

Polylib manipulates mixed inhomogeneous system of equations. The terms inhomogeneous stands for the fact that it manipulates objects of an affine space (not a linear space). To transform the inhomogeneous affine space of dimension $n$ into an homogeneous linear space of dimension $n+1$, we use the following mapping:

\begin{displaymath}{\cal M}: x \longrightarrow
\left(\begin{array}{c} \xi x \\ \xi \end{array}\right), \ \ \ \ \
\xi >0 \quad .\end{displaymath}

With this mapping, a system ${\cal P}=\{ x~\vert~ Ax=b,\ Cx\geq d \}$ in the original inhomogeneous space is transformed into ${\cal C}=\{ \tilde{x}~\vert~\tilde{A}\tilde{x}=0,\
\tilde{C}\tilde{x}\geq 0 \}$ where

\begin{displaymath}\tilde{A}=(A\ \ -b),\ \ \tilde{x}=
\begin{array}{cc} C & -d \\ 0 & 1
\end{array}\right) \quad .\end{displaymath}

In the internal representation of Polylib, object manipulated are cones (the Chernikova algorithm works on cones), but this is transparent for the user which naturally manipulates polyhedra (or union of polyhedra). As many Polylib functions refer to domain, we precisely define what a domain is:

Definition 2   (Domain) A polyhedral domain of dimension $n$ is defined as:
D:\{i\vert i\in Z^n, i\in P \}=Z^n \cap P
\end{displaymath} (3.1)

where $P$ is a union of polyhedra of dimension $n$.

next up previous contents
Next: Main functions in Polyhedron.c Up: Polyhedra Previous: Polyhedra   Contents
Sorin Olaru 2002-04-24