# Polyhedra and polytopes

Polyhedra are geometric objects that appear in mechanics to represent power constraints such as friction cones and maximum torque limits.

## Representations

A subset \(P \subset \mathbb{R}^d\) is called a (convex) *polyhedron* when
it is the set of solutions to a finite system of linear inequalities. In matrix
form:

where \(A\) is an \(n \times d\) matrix and \(b\) is a
\(d\)-dimensional vector (vector inequalities are componentwise). When a
polyhedron is bounded, it is called a *polytope*. To mark the difference
between 2D and higher dimensions, 2-dimensional polytopes are called
*polygons*.

### Halfspace representation

The *halfspace representation* (*H-rep* for short) is the description of the
polyhedron by inequalities:

It is always possible to normalize the representation so that the components of
\(b\) are either 1 or 0. When all these components are zero, the polyhedron
is a *polyhedral convex cone* pointed at the origin. When all the components of
\(b\) are ones, nothing can be said for sure... But, the other way round, a
polytope has only ones in the column vector of its H-rep. We therefore end up
with the following vocabulary:

In the 2D example to the right, the blue polygon is defined by four halfplanes. Here is a full H-rep of this polygon:

Normals corresponding to each supporting halfplane are depicted by red arrows (note that the length of the arrows is normalized on this drawing and does not correspond to that of the coordinates written next to it). Each line of the matrix \(A\) corresponds to one normal, while the corresponding column in \(b\) represents the affine offset between the halfplane and the origin.

### Vertex representation

The *vertex representation* (*V-rep* for short) of a polyhedron describes it in
terms of points (its *vertices*) and generating vectors called *rays*.
Informally, vertices are the "finite" boundaries of the polyhedron, while rays
are the "infinite" ones. A polytope has only vertices, while a polyhedral cone
has only rays. Formally, points \(x\) of the polyhedron are described by:

where \(\mathrm{conv}\) denotes the convex hull of a set of vertices \(V = \{ v_1, \ldots, v_p \}\):

while \(\mathrm{coni}\) is the conical hull of a set of rays \(R = \{ r_1, \ldots, v_q\}\):

In our 2D example to the right, the polyhedron is a polytope, so that \(R = \emptyset\). The four vertices of its V-rep are given by

In this particular case, the representation is unique, contrary to halfspace representations where each line can be multiplied by a positive constant without changing the underlying polyhedron. This uniqueness is basically only true for polytopes. In the general case where \(R \neq \emptyset\), rays can be scaled as well by positive constants without changing the underlying polyhedron.

## Double description

So far, we formally defined polyhedra from their H-rep, and introduced the V-rep. A fundamental result in polyhedral geometry states that these two representations are interchangeable:

Theorem (Minkowski and Weyl):any polyhedron can be equivalently described in halfspace or vertex representation. That is, for any set \(P = \{ x \ | \ A x \leq b\}\), there exists two sets \(V\) and \(R\) such that \(P = \mathrm{conv}(V) + \mathrm{coni}(R)\); and conversely.

From a computational standpoint, however, these two representations are not exactly equivalent. For example:

- With the
*halfspace*representation, it is easy to check whether a point \(x\) belongs to the polytope \((x \in P)\), but hard to sample points inside \(P\). - With the
*vertex*representation, it is hard to check whether \(x \in P\) (this amounts to solving a linear program) but easy to sample points inside \(P\) (using random values for the coefficients \(\alpha_i\) and \(\lambda_j\) in the convex and conic hulls, respectively).

Converting from a vertex to a halfspace representation is known as the *facet
enumeration problem*, while conversely converting from a halfspace to a vertex
representation is the *vertex enumeration problem*. These two problems are
actually equivalent when put under an appropriate mathematical formulation, and
can be solved using the *double description method*. The cdd library provides a C
implementation of this algorithm.

## To go further

### Good reads

- The excellent FAQ in Polyhedral Computation by Komei Fukuda.
- The first part of Christophe Weibel's thesis Minkowski sums of polytopes: combinatorics and computation gives a condensed introduction to polyhedra.
- The book Lectures on polytopes by Ziegler.
- The paper Double description method revisited by Fukuda and Prodon.

### Software

- pypoman: Python module to manipulate polyhedra using floating-point arithmetic (relies on
*cdd*) - Parma Polyhedra Library: C++ library to work with polyhedra using fractional numbers (slower but numerically stabler than
*cdd*) - pyparma: Python wrapper around the Parma Polyhedra Library

## Discussion

There are no comments yet. Feel free to leave a reply using the form below.