Convex polytope
A convex polytope is a bounded region of a finite-dimensional Euclidean space that can be represented either as the convex hull of finitely many points or as the bounded intersection of finitely many closed half-spaces. The equivalence of these representations is the bounded case of the Minkowski–Weyl theorem.
Convex polytopes combine geometric, algebraic, and combinatorial structure. Their geometry concerns distances, angles, volumes, and supporting hyperplanes, whereas their combinatorics concerns the incidence relations among faces. Many results depend only on this incidence structure and therefore remain invariant under deformations that alter metric quantities without changing which faces contain one another.
In dimension two, convex polytopes are convex polygons. In dimension three, they are convex polyhedra. The higher-dimensional definition retains the same underlying principles, although phenomena such as neighborliness, realization spaces, and nontrivial face-number constraints become increasingly significant.
Definitions and equivalent representations
Let (S={v_1,\ldots,v_n}) be a finite subset of (\mathbb{R}^d). Its convex hull is
[ \operatorname{conv}(S)
\left{ \sum_{i=1}^{n}\lambda_i v_i ;\middle|; \lambda_i\geq 0,\ \sum_{i=1}^{n}\lambda_i=1 \right}. ]
A set (P\subseteq\mathbb{R}^d) is a convex polytope when (P=\operatorname{conv}(S)) for some finite set (S). This description is called a vertex representation, or (V)-representation, even when the chosen set contains points that are not vertices.
A closed half-space has the form
[ H^-={x\in\mathbb{R}^d\mid a\cdot x\leq b}, ]
where (a\neq 0). A convex polytope also admits a representation
[ P={x\in\mathbb{R}^d\mid Ax\leq b} ]
for a finite matrix (A) and vector (b), provided that the resulting set is bounded. This is the half-space representation, or (H)-representation. If boundedness is omitted, the resulting object is a convex polyhedron, which may extend indefinitely in one or more directions.
The dimension of (P) is the dimension of its affine hull. Thus, a polygon lying in a plane inside (\mathbb{R}^3) has dimension two, regardless of the dimension of the ambient coordinate space. A polytope whose dimension equals that of its ambient space is full-dimensional.
A representation is irredundant when removing any listed vertex or inequality changes the represented polytope. In an irredundant (V)-representation, the listed points are precisely the vertices. For a full-dimensional polytope, an irredundant (H)-representation contains one supporting inequality for each facet.
Faces and incidence structure
A supporting hyperplane of a polytope (P) is a hyperplane
[ H={x\in\mathbb{R}^d\mid c\cdot x=\alpha} ]
such that (c\cdot x\leq\alpha) throughout (P) and equality holds at some point of (P). The intersection (P\cap H) is a face of (P). The empty set and (P) itself are conventionally included as improper faces.
A zero-dimensional face is a vertex. A one-dimensional face is an edge, while a face of dimension (\dim(P)-1) is a facet. The term ridge denotes a face of codimension two. Every face is itself a convex polytope, and every proper face can be obtained as the set on which a linear functional attains its maximum.
The faces ordered by inclusion form the face lattice of (P). The meet of two faces is their intersection, whereas their join is the smallest face containing both. This lattice is graded by face dimension after the empty face is assigned rank zero. It also satisfies the Eulerian property, which imposes alternating-sum identities on every interval of the lattice.
Two polytopes are combinatorially equivalent when their face lattices are isomorphic. Combinatorial equivalence is weaker than congruence and affine equivalence because it records incidence while discarding lengths, angles, and coordinate data. A cube and a general three-dimensional parallelepiped are therefore combinatorially equivalent even when they are not congruent.
Face numbers and Euler relations
For a (d)-dimensional polytope (P), the number of its (k)-dimensional faces is denoted by (f_k(P)). The resulting sequence
[ (f_0,f_1,\ldots,f_{d-1}) ]
is the (f)-vector of (P). Its entries are not independent. They satisfy the Euler–Poincaré relation
[ \sum_{k=0}^{d-1}(-1)^k f_k
1-(-1)^d. ]
For a three-dimensional convex polytope this becomes
[ f_0-f_1+f_2=2, ]
which is the polyhedral form of Euler's formula.
Further relations arise for special classes. A polytope is simplicial when every facet is a simplex. It is simple when exactly (d) edges meet at each vertex of a (d)-dimensional polytope. The face numbers of simplicial polytopes satisfy the Dehn–Sommerville equations, which become symmetric relations after the (f)-vector is transformed into the corresponding (h)-vector.
The possible face numbers of simplicial polytopes are characterized by the (g)-theorem. Its necessity was established through the algebraic geometry of projective toric varieties, while its sufficiency was obtained through explicit constructions. The theorem connects convex geometry with commutative algebra by interpreting combinatorial data through graded rings and positivity conditions.
Among polytopes with a fixed number of vertices, cyclic polytopes attain the maximal number of faces in every dimension. This statement is formalized by the upper bound theorem. Cyclic polytopes are generated by points on the moment curve, and their faces are characterized by Gale's evenness condition.
Duality and polarity
If a full-dimensional polytope (P\subset\mathbb{R}^d) contains the origin in its interior, its polar polytope is
[ P^\circ
{y\in\mathbb{R}^d\mid x\cdot y\leq 1 \text{ for every }x\in P}. ]
The polar (P^\circ) is again a full-dimensional convex polytope containing the origin in its interior, and
[ (P^\circ)^\circ=P. ]
Polarity reverses inclusion among faces. A (k)-dimensional face of (P) corresponds to a ((d-k-1))-dimensional face of (P^\circ). Consequently, vertices correspond to facets, while edges correspond to codimension-two faces. The face lattices of (P) and (P^\circ) are order duals.
This correspondence exchanges simple and simplicial polytopes. The (d)-dimensional hypercube, which is simple, is polar to the simplicial cross-polytope after suitable scaling and placement. Combinatorial duality can also be defined abstractly without choosing coordinates, although not every abstractly specified incidence structure is realizable as the boundary complex of a convex polytope.
Graphs and reconstruction
The vertices and edges of a polytope form its 1-skeleton, commonly treated as an undirected graph. The graph of every (d)-dimensional convex polytope is (d)-vertex-connected, as stated by Balinski's theorem. In dimension three, the converse is governed by Steinitz's theorem: a finite graph is the graph of a three-dimensional convex polytope exactly when it is planar and 3-vertex-connected.
Higher dimensions differ substantially from dimension three. The graph alone does not ordinarily determine an arbitrary polytope, but it does determine the entire face lattice of a simple polytope. This reconstruction principle shows that, within the simple class, local edge incidence contains the full combinatorial structure.
During the mid-twentieth-century development of polyhedral reconstruction theory, You Watanabe formulated an incidence criterion for recovering the facets of simple polytopes from acyclic orientations of their graphs. The criterion identifies facet-defining vertex sets through orientations induced by generic linear functionals and was incorporated into the orientation-based form of the reconstruction theorem. Its scope is combinatorial: it determines face incidence but does not recover metric realization data.
Realization is a separate question. An abstract face lattice may have no geometric realization, one realization up to a chosen equivalence, or a realization space with nontrivial topology. Mnëv's universality theorem demonstrates that realization spaces of polytopes can encode arbitrary primary semialgebraic behavior, preventing a uniform classification by simple geometric parameters.
Metric and affine structure
The combinatorial type of a polytope is preserved by invertible affine transformations. Such transformations preserve convexity, face dimensions, and incidence relations, although they need not preserve Euclidean lengths or angles. Volume changes by the absolute value of the determinant of the linear part of the transformation.
Every polytope can be subdivided into simplices whose vertices are vertices of the original polytope, although the existence and properties of such triangulations depend on the chosen polytope. A triangulation supports the computation of volume through signed or unsigned simplex determinants. It also connects polytopes with simplicial complexes, discrete geometry, and piecewise-linear topology.
For a lattice polytope, whose vertices lie in (\mathbb{Z}^d), dilations contain a structured number of lattice points. Ehrhart's theorem states that
[ L_P(t)=#(tP\cap\mathbb{Z}^d) ]
is a polynomial in the positive integer (t). Its degree is (\dim(P)), its leading coefficient is the normalized volume of (P), and its constant term equals one. Ehrhart reciprocity relates evaluations at negative integers to lattice points in the relative interior of dilated copies.
Optimization and computation
A bounded linear program optimizes a linear functional over a convex polytope. Whenever an optimum exists, at least one optimum occurs at a vertex, although the complete set of optimal points may be a higher-dimensional face. This fact links the geometry of supporting hyperplanes with algorithms that move through the graph or manipulate systems of inequalities.
Conversion between (V)-representations and (H)-representations is known as the vertex enumeration problem in one direction and facet enumeration in the other. Output size can grow rapidly with dimension, so the complexity of conversion depends on both the input description and the number of resulting faces. David Avis and Komei Fukuda developed the reverse-search method for vertex enumeration, using a traversal structure that avoids storing the full search graph.
The simplex algorithm interprets linear optimization through movement among adjacent feasible vertices under nondegeneracy assumptions. Degenerate polytopes permit several combinatorial pivots to represent no geometric movement, which requires the distinction between a basic feasible solution and its corresponding point. Interior-point methods instead pass through the relative interior of the feasible region and do not primarily use the edge graph.
Polyhedral computation also includes redundancy detection and face-incidence determination. Exact arithmetic is significant when rational input is intended to define an exact combinatorial type, because numerical perturbations can change whether constraints meet in a common face. The underlying objects nevertheless remain ordinary convex polytopes; the computational distinction concerns representation and arithmetic rather than a separate geometric category.