A convex polytope may be defined in a number of ways, depending on what is more suitable for the problem at hand. Grünbaum's definition is in terms of a convex set of points in space. Other important definitions are: as the
intersection of
half-spaces (half-space representation) and as the
convex hull of a set of points (vertex representation).
Vertex representation (convex hull) In his book
Convex Polytopes, Grünbaum defines a convex polytope as a
compact convex set with a finite number of extreme points: : A set K of \mathbb{R}^n is
convex if, for each pair of distinct points a, b in K, the closed segment with endpoints a and b is contained within K. This is equivalent to defining a bounded convex polytope as the
convex hull of a finite set of points, where the finite set must contain the set of extreme points of the polytope. Such a definition is called a
vertex representation (
V-representation or
V-description). :a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b where n is the dimension of the space containing the polytope under consideration. Hence, a
closed convex polytope may be regarded as the set of solutions to the
system of linear inequalities: :\begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; \leq \;&&& b_1 \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; \leq \;&&& b_2 \\ \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; \leq \;&&& b_m \\ \end{alignat} where m is the number of half-spaces defining the polytope. This can be concisely written as the
matrix inequality: :Ax \leq b where A is an m\times n matrix, x is an n\times1 column vector whose coordinates are the variables x_1 to x_n, and b is an m\times1 column vector whose coordinates are the right-hand sides b_1 to b_m of the scalar inequalities. An
open convex polytope is defined in the same way, with strict inequalities used in the formulas instead of the non-strict ones. The coefficients of each row of A and b correspond with the coefficients of the linear inequality defining the respective half-space. Hence, each row in the matrix corresponds with a
supporting hyperplane of the polytope, a hyperplane bounding a half-space that contains the polytope. If a supporting hyperplane also intersects the polytope, it is called a
bounding hyperplane (since it is a supporting hyperplane, it can only intersect the polytope at the polytope's boundary). The foregoing definition assumes that the polytope is full-dimensional. In this case, there is a
unique minimal set of defining inequalities (up to multiplication by a positive number). Inequalities belonging to this unique minimal system are called
essential. The set of points of a polytope which satisfy an essential inequality with equality is called a
facet. If the polytope is not full-dimensional, then the solutions of Ax\leq b lie in a proper
affine subspace of \mathbb{R}^n and the polytope can be studied as an object in this subspace. In this case, there exist linear equations which are satisfied by all points of the polytope. Adding one of these equations to any of the defining inequalities does not change the polytope. Therefore, in general there is no unique minimal set of inequalities defining the polytope. In general the intersection of arbitrary half-spaces need not be bounded. However if one wishes to have a definition equivalent to that as a convex hull, then bounding must be explicitly required.
Equivalence to the vertex representation By requiring that the intersection of half-spaces results in a bounded set, the definition becomes equivalent to the vertex-representation. An outline of the proof, that the bounded intersection of half-spaces results in a polytope in vertex-representation, follows: The
bounded intersection of
closed half-spaces of \mathbb{R}^n is clearly compact and convex. A compact and convex set with a finite number of extreme points must be a polytope, where those
extreme points form the set of vertices. It remains to show that the set of extreme points (of the bounded intersection of a finite set of half-spaces) is also finite: Let x \in \textrm{ext}(P) be an extreme point of P := \bigcap_{i=1}^{k} H_i, the bounded intersection of closed half-spaces H_i. We consider the intersection of all the corresponding hyperplanes (which divide the space into the half-spaces) that contain x. This yields an affine subspace U. For each half-space where the hyperplane does not contain x, we consider the intersection of the
interior of those half-spaces. This yields an open set O. Clearly, x \in (U \cap O) \subseteq P. Since x is an extreme point of P and D := U \cap O is
relatively open, it follows that D must be 0-dimensional and D = \left\{ x \right\}. If D was not 0-dimensional, x would be the inner point of (at least) a line, which contradicts x being an extreme point. Since every construction of D chooses either the interior or the boundary of one of the k closed half-spaces, there are only finitely many different sets D. Every extreme point lies in one of these sets, which means that the amount of extreme points is finite.
Using the different representations The two representations together provide an efficient way to decide whether a given vector is included in a given convex polytope: to show that it is in the polytope, it is sufficient to present it as a convex combination of the polytope vertices (the V-description is used); to show that it is not in the polytope, it is sufficient to present a single defining inequality that it violates. A subtle point in the representation by vectors is that the number of vectors may be exponential in the dimension, so the proof that a vector is in the polytope might be exponentially long. Fortunately,
Carathéodory's theorem guarantees that every vector in the polytope can be represented by at most
d+1 defining vectors, where
d is the dimension of the space.
Representation of unbounded polytopes For an unbounded polytope (sometimes called: polyhedron), the H-description is still valid, but the V-description should be extended.
Theodore Motzkin (1936) proved that any unbounded polytope can be represented as a sum of a
bounded polytope and a
convex polyhedral cone. In other words, every vector in an unbounded polytope is a
convex sum of its vertices (its "defining points"), plus a
conical sum of the
Euclidean vectors of its infinite edges (its "defining rays"). This is called the
finite basis theorem. ==Properties==