Facet Complexity

An ''n''-dimensional polyhedron is a geometric object that generalizes the 3-dimensional polyhedron to an ''n''-dimensional space. It is defined as a set of points in real affine (or Euclidean) space of any dimension ''n'', that has flat sides. It may alternatively be defined as the intersection of finitely many half-spaces. Unlike a 3-dimensional polyhedron, it may be bounded or unbounded. In this terminology, a bounded polyhedron is called a polytope...

Analytically, a convex polyhedron is expressed as the solution set for a system of linear inequalities, ''a_i''^T''x'' ≤ ''b_i'', where ''a_i'' are vectors in R^''n'' and ''b_i'' are scalars. This definition of polyhedra is particularly important as it provides a geometric perspective for problems in linear programming.

Examples

Many traditional polyhedral forms are n-dimensional polyhedra. Other examples include:

* A half-space is a polyhedron defined by a single linear inequality, ''a₁''^T''x'' ≤ ''b₁''.
* A hyperplane is a polyhedron defined by two inequalities, ''a₁''^T''x'' ≤ ''b₁'' and ''a₁''^T''x'' ≥ ''b₁'' (which is equivalent to ''-a₁''^T''x'' ≤ -''b₁'').
* A quadrant in the plane. For instance, the region of the cartesian plane consisting of all points above the horizontal axis and to the right of the vertical axis: . Its sides are the two positive axes, and it is otherwise unbounded.
* An octant in Euclidean 3-space, .
* A prism of infinite extent. For instance a doubly infinite square prism in 3-space, consisting of a square in the ''xy''-plane swept along the ''z''-axis: .
* Each cell in a Voronoi tessellation is a polyhedron. In the Voronoi tessellation of a set ''S'', the cell ''A'' corresponding to a point is bounded (hence a traditional polyhedron) when ''c'' lies in the interior of the convex hull of ''S'', and otherwise (when ''c'' lies on the boundary of the convex hull of ''S'') ''A'' is unbounded.

Faces and vertices

A subset ''F'' of a polyhedron ''P'' is called a face of ''P'' if there is a halfspace ''H'' (defined by some inequality ''a₁''^T''x'' ≤ ''b₁'') such that ''H'' contains ''P'' and ''F'' is the intersection of ''H'' and ''P''.

* If a face contains a single point , then ''v'' is called a vertex of ''P''.
* If a face ''F'' is nonempty and ''n''-1 dimensional, then ''F'' is called a facet of ''P''.
Suppose ''P'' is a polyhedron defined by ''Ax'' ≤ ''b'', where ''A'' has full column rank. Then, ''v'' is a vertex of ''P'' if and only if ''v'' is a basic feasible solution of the linear system ''Ax'' ≤ ''b''.

Standard representation

The representation of a polyhedron by a set of linear inequalities is not unique. It is common to define a standard representation for each polyhedron ''P'':

* If ''P'' is full-dimensional, then its standard representation is a set of inequalities such that each inequality ''a_i''^T''x'' ≤ ''b_i'' defines exactly one facet of ''P'', and moreover, the inequalities are normalized such that $\, a_i \, _ = 1$ for all ''i''.
* If ''P'' is not full-dimensional, then it is contained in its affine hull, which is defined by a set of linear equations ''C''x=''d''. It is possible to choose ''C'' such that ''C'' = (''I'', ''C'''), where ''I'' is an identity matrix. The standard representation of ''P'' contains this set ''C''x=''d'' and a set of inequalities such that each inequality ''a_i''^T''x'' ≤ ''b_i'' defines exactly one facet of ''P'', the inequalities are normalized such that $\, a_i \, _ = 1$ for all ''i'', and each ''a_i'' is orthogonal to each row of ''C''. This representation is unique up to the choice of columns of the identity matrix.

Representation by cones and convex hulls

If ''P'' is a polytope (a bounded polyhedron), then it can be represented by its set of vertices ''V'', as ''P'' is simply the convex hull of ''V'': ''P'' = conv(''V'').

If ''P'' is a general (possibly unbounded) polyhedron, then it can be represented as: P = conv(V) + cone(E), where ''V'' is (as before) the set of vertices of ''P'', and ''E'' is another finite set, and cone denotes the conic hull. The set cone(E) is also called the recession cone of ''P''.

Carathéodory's theorem states that, if ''P'' is a ''d''-dimensional polytope, then every point in ''P'' can be written as a convex combination of at most ''d''+1 affinely-independent vertices of ''P''. The theorem can be generalized: if ''P'' is any ''d''-dimensional polyhedron, then every point in ''P'' can be written as a convex combination of points ''v''₁,...,''v_s'', ''v''₁+''e''₁,...,''v''₁+''e_t'' with ''s''+''t'' ≤ ''d''+1, such that ''v''₁,...,''v_s'' are elements of minimal nonempty faces of ''P'' and ''e''₁,...,''e_t'' are elements of the minimal nonzero faces of the recession cone of ''P''.

Complexity of representation

When solving algorithmic problems on polyhedra, it is important to know whether a certain polyhedron can be represented by an encoding with a small number of bits. There are several measures to the representation complexity of a polyhedron ''P'':

* ''P'' has facet complexity at most ''f'', if ''P'' can be represented by a system of linear inequalities with rational coefficients, such that the encoding length of each inequality (i.e., the binary encoding length of all rational numbers appearing as coefficients in the inequality) is at most ''f''. Note that ''f ≥ n''+1, since there are n+1 coefficients in each inequality.
* P has vertex complexity at most ''v'', if ''P'' can be represented as conv(''V'')+cone(''E''), where ''V'' and ''E'' are finite sets, such that each point in V or E has encoding length at most ''v''. Note that ''v ≥ n'', since there are ''n'' coefficients in each vector.
These two kinds of complexity are closely related:

*If ''P'' has facet complexity at most ''f'', then P has vertex complexity at most 4 ''n''² ''f''.
*If ''P'' has vertex complexity at most ''v'', then P has facet complexity at most 3 ''n''² ''v''.

A polyhedron ''P'' is called well-described if we know ''n'' (the number of dimensions) and ''f'' (an upper bound on the facet complexity). This is equivalent to requiring that we know ''n'' and ''v'' (an upper bound on the vertex complexity).

In some cases, we know an upper bound on the facet complexity of a polyhedron ''P'', but we do not know the specific inequalities that attain this upper bound. However, it can be proved that the encoding length in any standard representation of ''P'' is at most 35 ''n''² ''f''.

The complexity of representation of ''P'' implies upper and lower bounds on the volume of ''P'':

* If ''P'' has vertex complexity at most ''v'', then trivially, all vertices of ''P'' are contained in the ball of radius 2^v around the origin. This means that, if ''P'' is a polytope, then P itself is circumscribed in that ball.
* If ''P'' is a full-dimensional polyhedron with facet complexity at most ''f'', then ''P'' contains a ball with radius $2^$. Moreover, this ball is contained in the ball of radius $2^$ around the origin.
Small representation complexity is useful for "rounding" approximate solutions to exact solutions. Specifically:

* If ''P'' is a polyhedron with facet complexity at most ''f'', and ''y'' is a rational vector whose entries have common denominator at most ''q'', and the distance from ''y'' to ''P'' is at most 2^-2''f''/''q'', then ''y'' is in fact in ''P''.
* If ''P'' is a polyhedron with vertex complexity at most ''v'', and ''P'' satisfies the inequality ''a''^T''x'' ≤ ''b + 2^-v-1,'' then ''P'' also satisfies the inequality ''a''^T''x'' ≤ ''b.''
* If ''P'' is a polyhedron with facet complexity at most ''f'', and ''v'' is a rational vector with distance from ''P'' of at most 2^-6n''f'', and ''q'' and ''w'' are integer vectors satisfying \, qv-w \, < 2^, 0, then the point ''w''/''q'' is contained in ''P''. The number ''q'' and the vector ''w'' can be found in polytime using simultaneous diophantine approximation.
* If ''P'' is a polyhedron with vertex complexity at most ''v'', and ''P'' satisfies the inequality ''a''^T''x'' ≤ ''b + 2^-6nv,'' and q,c,d are integer vectors satisfying \, qa-c \, + , qb-d, < 2^, 0, then ''P'' satisfies the inequality c^T''x'' ≤ ''d''. The numbers ''q,d'' and the vector ''c'' can be found in polytime using simultaneous diophantine approximation.

See also

* Algorithmic problems on convex sets

References

{{reflist

Polyhedra
Linear programming