Theoretical background

A nonempty set of points in a Euclidean space is called a (*convex*) *cone* if
whenever and
. A cone is *polyhedral* if

for some matrix , i.e. if is the intersection of finitely many linear half-spaces. Results from the linear programming theory [SCH86] shows that the concepts of

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.

Hence, a set of vectors in is called a *(convex)
polyhedron* if:

for some matrix and a vector , i.e 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.

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

In Polylib the decomposition theorem is extensively used (in
its extended form for polyhedra). A polyhedron can be
represented by a set of inequalities (usually, implicit equalities are
represented in a separate matrix):
, this
representation is called *implicit*. From the Minkovski
characterization, we know that has a dual representation, called
the *parametric representation*.

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

- a linear
combination of so called
*lines*(columns of matrix ), - a
convex combination of
*vertices*(columns of matrix ), and - a positive combination of
*extremal rays*(columns of matrix ).

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].

- The
*characteristic cone*of a polyhedron is the polyhedral cone

Sometimes the characteristic cone is called the

*recession cone of*. If , with a polytope an a polyhedral cone, then . - The
*lineality space*of is the linear space

If the lineality space has dimension zero, is said to be*pointed*. - A
*supporting hyperplane*of is the affine hyperplane described by where is a nonzero vector and . - A subset of a polyhedron
is called a face if or if is the intersection of with a
supporting hyperplane of . In other words is a face if and only
if there is a vector for which is the set of vectors attaining
provided that this maximum is finite.
A alternative description of a face is the nonempty subset :

for some subsystem of . - The faces of a polyhedron have the following important properties:
- has finitely many faces;
- each face is a nonempty polyhedron;
- if is a face of and , then: is a face of if and only if is a face of .

- A
*facet*of is a maximal face distinct from . In other words if there is no redundant inequality in the polyhedron definition system: then there exists a one-to-one correspondence between the facets of and the inequalities given by

for any facet of and any inequality from .The faces of dimension , , and are called

*the vertices, edges, ridges*and*facets*, respectively. The vertices coincide with the extremal points of the polyhedron, that are also defined as points which cannot be represented as convex combinations of two other points in the polyhedron. When an edge is not bounded, there are two cases: either it is a line or a half-line starting from a vertex. A half-line edge is called an extremal ray. - The
*convex hull*of a set is the convex combination of all points in . It is the smallest convex set which contains all of .

Polylib implements procedures to compute, from one representation of a polyhedron (implicit of parametric), its dual representation of , 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 into an
homogeneous linear space of dimension , we use the following
mapping:

With this mapping, a system in the original inhomogeneous space is transformed into where

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:

(3.1) |