Next: Main functions in Polyhedron.c Up: Polyhedra Previous: Polyhedra   Contents

# 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 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 , it is called a -polyhedron (-polytope).

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.

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

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:

Lemma 1   Let be a matrix and let be a vector. Then the system of linear inequalities has a solution , if and only of for each row vector with .

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:

Definition 2   (Domain) A polyhedral domain of dimension is defined as:
 (3.1)

where is a union of polyhedra of dimension .

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