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, aiTx ≤ bi, where ai are vectors in Rn and bi 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, a1Tx ≤ b1. A hyperplane is a polyhedron defined by two inequalities, a1Tx ≤ b1 and a1Tx ≥ b1 (which is equivalent to -a1Tx ≤ -b1). 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: { ( x, y ) : x ≥ 0, y ≥ 0 }. Its sides are the two positive axes, and it is otherwise unbounded. An octant in Euclidean 3-space, { ( x, y, z ) : x ≥ 0, y ≥ 0, z ≥ 0 }. 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: { ( x, y, z ) : 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 }. Each cell in a Voronoi tessellation is a polyhedron. In the Voronoi tessellation of a set S, the cell A corresponding to a point c ∈ S 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 non-empty subset F of a polyhedron P is called a face of P if F=P or there is a halfspace H (defined by some inequality a1Tx ≤ b1) such that H contains P and F is the intersection of the boundary 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 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 aiTx ≤ bi defines exactly one facet of P, and moreover, the inequalities are normalized such that ‖ a i ‖ ∞ = 1 {\displaystyle \|a_{i}\|_{\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 aiTx ≤ bi defines exactly one facet of P, the inequalities are normalized such that ‖ a i ‖ ∞ = 1 {\displaystyle \|a_{i}\|_{\infty }=1} for all i, and each ai 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 v1,...,vs, v1+e1,...,v1+et with s+t ≤ d+1, such that v1,...,vs are elements of minimal nonempty faces of P and e1,...,et 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 n2 f. If P has vertex complexity at most v, then P has facet complexity at most 3 n2 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 n2 f. The complexity of representation of P implies upper and lower bounds on the volume of P:
… excerpt ends here. Continue reading the full article.
