N-dimensional polyhedron

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₁^Tx ≤ b₁) such that H contains P and F is the intersection of H and P.

• If a face contains a single point {v}, 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^Tx ≤ b_i defines exactly one facet of P, and moreover, the inequalities are normalized such that ${\displaystyle \Vert a_i{\Vert }_{\mathrm{\infty }}=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 Cx=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 Cx=d and a set of inequalities such that each inequality a_i^Tx ≤ b_i defines exactly one facet of P, the inequalities are normalized such that ${\displaystyle \Vert a_i{\Vert }_{\mathrm{\infty }}=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 ${\displaystyle 2^{-7n^{3}f}}$. Moreover, this ball is contained in the ball of radius ${\displaystyle 2^{5n^{2}f}}$ 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^-2f/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^Tx ≤ b + 2^-v-1, then P also satisfies the inequality a^Tx ≤ 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^-6nf, and q and w are integer vectors satisfying ${\displaystyle \Vert qv-w\Vert <2^{-3f},0<q<2^{4nf}}$, 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^Tx ≤ b + 2^-6nv, and q,c,d are integer vectors satisfying ${\displaystyle \Vert qa-c\Vert +|qb-d|<2^{-3v},0<q<2^{4nv}}$, then P satisfies the inequality c^Tx ≤ d. The numbers q,d and the vector c can be found in polytime using simultaneous diophantine approximation.