A polytope is a geometric object that generalizes a polygon in two dimensions and a bounded polyhedron in three dimensions to arbitrary finite dimension. In its most common modern meaning, a convex polytope is the convex hull of finitely many points in a real Euclidean space. Equivalently, it is a bounded intersection of finitely many closed half-spaces. These two descriptions—one by points, the other by inequalities—connect its geometric shape with algebraic representation and computation.
Polytopes are fundamental objects in geometry, combinatorics, and mathematical optimization. Their faces encode finite incidence structures; their volumes and lattice points connect geometry with arithmetic; and their edges describe possible steps in important optimization algorithms. Familiar examples include triangles, cubes, and tetrahedra, but high-dimensional polytopes also represent probability distributions, transportation plans, schedules, and solutions to discrete optimization problems.
Terminology depends on context. Convex geometry usually reserves “polytope” for the convex, bounded objects described above. Other branches study nonconvex, star, or abstract polytopes, where incidence relations and symmetry may matter more than a solid region in space. Unless otherwise specified, the discussion below concerns nonempty convex polytopes.
Definitions and finite representations
Let be points in . Their convex hull is
A set of this form is a polytope. Each point of is a convex combination of the generators, and the line segment joining any two points of lies entirely in . Thus every convex polytope is a convex set. Some generators may be redundant: adding an interior point to the defining list does not change the convex hull.
The equivalent inequality description has the form
provided this set is bounded. Here is a real matrix, and each row specifies a closed half-space. Equalities can be represented by pairs of opposite inequalities, although keeping them separate is often computationally preferable. A general finite intersection of closed half-spaces is a polyhedron, which need not be bounded. For example, the nonnegative orthant is a polyhedron but not a polytope. The equivalence between the finite convex-hull description and the bounded inequality description is a fundamental consequence of the Minkowski–Weyl theorem.
The dimension of is the dimension of its affine hull, the smallest affine space containing it. A triangle embedded in is therefore two-dimensional, not three-dimensional. A polytope is full-dimensional when its affine hull is the entire ambient space. Many theorems are most naturally stated within the affine hull, where a lower-dimensional polytope becomes full-dimensional. In particular, its relative interior consists of its interior points with respect to that affine hull.
Convex polytopes are closed and bounded, hence compact. They have finitely many vertices, and they are precisely the convex hulls of those vertices. By contrast, a disk is compact and convex but not a polytope: its circular boundary has infinitely many extreme points. Boundedness and finite generation are therefore independent aspects of the definition, not consequences of convexity alone.
Two standard data formats reflect the equivalent definitions. A V-representation lists vertices or other generating points, whereas an H-representation lists linear inequalities and, if necessary, equations. Passing between these formats is mathematically straightforward in principle but can be computationally expensive. A polytope may have relatively few vertices and very many facets, or the reverse, so one representation can be exponentially larger than the other.
Faces, incidence, and local structure
A proper nonempty face of a polytope is the set on which some nonconstant linear functional attains its maximum:
Geometrically, a supporting hyperplane touches the polytope without cutting through its relative interior, and its intersection with the polytope is a face. The empty face and itself are also included by convention. Every nonempty face is again a polytope.
Faces of dimensions , , and are called vertices, edges, and two-dimensional faces. For a -dimensional polytope, faces of dimension are facets, and those of dimension are ridges. A three-dimensional cube has eight vertices, twelve edges, and six facets. In a four-dimensional polytope, the facets are three-dimensional polyhedra, so the word “face” is not restricted to flat polygonal panels.
The faces, ordered by inclusion, form the face lattice. This structure records which vertices lie on which edges, which edges lie in which higher-dimensional faces, and so forth. Two polytopes are combinatorially equivalent when their face lattices are isomorphic. This is weaker than congruence or affine equivalence: a square and a nonrectangular convex quadrilateral have the same face lattice even though their lengths and angles differ. The face lattice therefore separates incidence information from a particular geometric realization.
Local structure near a vertex can be examined using a vertex figure. A hyperplane that separates a vertex from all other vertices, chosen sufficiently close to it, cuts the polytope in a -dimensional polytope. Faces of this section correspond to faces containing the original vertex, with dimension reduced by one. A cube has triangular vertex figures; an octahedron has square vertex figures. This construction translates questions about neighborhoods of vertices into lower-dimensional polytope theory.
A -polytope is simple if each vertex lies on exactly edges, equivalently exactly facets. It is simplicial if every facet is a simplex. Cubes are simple, while octahedra are simplicial. These conditions are dual rather than synonymous, and a simplex satisfies both.
The vertices and edges form the polytope’s graph, an object of graph theory. Balinski’s theorem states that the graph of a -polytope is -vertex-connected: deleting fewer than vertices cannot disconnect it. In dimension three, Steinitz’s theorem gives a complete graph-theoretic characterization: a finite graph is the graph of a convex three-dimensional polytope exactly when it is planar and three-vertex-connected.
Fundamental families and symmetry
The simplex is the smallest full-dimensional polytope in each dimension. A -simplex is the convex hull of affinely independent points. Its low-dimensional examples are a segment, a triangle, and a tetrahedron. Every subset of its vertices determines a face, so its number of -dimensional faces is
Simplices are particularly important because more complicated polytopes can be subdivided into them, and because affine coordinates on a simplex give a natural way to express interpolation and probability weights.
The hypercube and cross-polytope form another basic pair. Standard coordinate models are
where are the coordinate unit vectors. The hypercube has vertices and facets; the cross-polytope has vertices and facets. In three dimensions these are the cube and octahedron. More generally, the hypercube has
faces of dimension : choose the freely varying coordinates and fix each remaining coordinate at either endpoint.
A regular polytope has a symmetry group acting transitively on its flags, where a flag is a maximal chain of incident faces. In Euclidean geometry, the relevant symmetries are distance-preserving transformations, and their organization is studied through group theory. There are infinitely many regular convex polygons in dimension two, five regular convex polyhedra in dimension three, and six regular convex polytopes in dimension four. The exceptional four-dimensional examples include the 24-cell, 120-cell, and 600-cell. In every dimension at least five, only three regular convex types remain: the simplex, hypercube, and cross-polytope.
Regularity is much more restrictive than having congruent facets or identical-looking vertices. A rectangular box with unequal edge lengths has the combinatorial type of a cube but lacks the cube’s full Euclidean symmetry. Conversely, combinatorial automorphisms of a face lattice need not all be realized as isometries of a particular geometric embedding. The distinction between geometric symmetry and combinatorial symmetry becomes especially important for abstract polytopes.
Several less symmetric families play major structural roles. A cyclic polytope is the convex hull of finitely many points on the moment curve
It is highly neighborly: every set of at most vertices forms a face. A zonotope is a sum of line segments; cubes and many centrally symmetric polytopes belong to this family. Permutahedra, formed from permutations of coordinate lists, and associahedra, whose vertices encode parenthesizations or polygon triangulations, connect polytope geometry with discrete structures.
Polarity and geometric constructions
For a full-dimensional polytope containing the origin in its interior, its polar is
Here denotes the Euclidean inner product. The polar is again a full-dimensional polytope containing the origin in its interior, and . The placement of the origin matters: translating a polytope generally changes the shape of its polar, even though the original translation does not change its face lattice.
Polar duality reverses incidence. A nonempty proper -face of corresponds to a -face of . Vertices correspond to facets, edges correspond to codimension-two faces, and inclusions reverse direction. For the coordinate models above, the polar of the hypercube is the cross-polytope. More generally, the polar of a simple polytope is simplicial, and the polar of a simplicial polytope is simple. The duality of face lattices does not require the two geometric objects to be congruent or even affinely equivalent.
Several constructions build new polytopes from old ones. The Cartesian product has dimension ; the product of a polygon with a segment is a prism. A pyramid is obtained by taking the convex hull of and one point outside its affine hull. Its dimension is one greater than that of . Repeated pyramiding over a point constructs simplices, while repeated products with segments construct hypercubes. A bipyramid instead places two apex points on opposite sides of a base polytope in a compatible configuration.
The Minkowski sum is defined by
It is a polytope whenever and are polytopes. Its support function,
satisfies . This identity explains how supporting hyperplanes behave under addition. Zonotopes are precisely Minkowski sums of finitely many segments, making their geometry closely related to arrangements of hyperplanes.
An affine map sends a polytope to a polytope, although dimension and face structure may collapse. Sections by affine subspaces are also polytopes when nonempty. Projections can merge vertices and erase facets, while sections can create vertices at intersections with higher-dimensional faces. These operations are central to extended formulations: a polytope that requires many inequalities in its own coordinates may be the projection of a higher-dimensional polytope with a much shorter description.
Face numbers, topology, and extremal bounds
The -vector of a -polytope is
where counts its -dimensional faces. These numbers satisfy strong constraints. The most familiar is the Euler relation,
For a three-dimensional polytope this becomes . For a polygon it gives . The empty face is often assigned dimension and count , which simplifies more general identities.
The topological explanation is that the boundary of a -polytope is homeomorphic to the sphere . Radial projection from an interior point gives such a homeomorphism. The alternating face count is consequently its Euler characteristic. The polytope itself is homeomorphic to a closed -dimensional ball. These facts connect finite face enumeration with topology, while the face decomposition supplies concrete cells on which topological invariants can be computed.
For a simplicial polytope, face numbers are frequently reorganized into the -vector, defined by
The Dehn–Sommerville relations assert that . They generalize the Euler relation and express a symmetry not immediately visible in the original face counts. The -vector also links polytope combinatorics to graded algebra, where its entries can appear as dimensions of graded components of associated algebraic objects.
The upper bound theorem states that, among -polytopes with a fixed number of vertices, cyclic polytopes maximize the number of faces in every dimension. Peter McMullen proved the theorem in 1970. The result provides sharp limits on how complicated the boundary can be when the vertex count is fixed. Lower bound theorems, under appropriate hypotheses, identify opposite extremal behavior; stacked simplicial polytopes, built by repeatedly attaching simplices along facets, play a central role.
For simplicial polytopes, the -theorem gives a complete characterization of possible face vectors through conditions on differences . Its proof emerged around 1980 from work by Louis Billera and Carl Lee on sufficiency and Richard Stanley on necessity. Stanley’s argument used algebraic geometry, revealing that inequalities between face counts can reflect deep algebraic structure.
For general nonsimplicial polytopes, a comparably complete characterization remains unavailable. Ordinary face numbers also omit information about chains of incident faces. Flag vectors record such chains and distinguish incidence patterns that the -vector cannot, leading to a richer enumeration problem in higher dimensions.
Volume, lattice points, and arithmetic
The volume of a full-dimensional polytope is its -dimensional Euclidean measure; for a lower-dimensional polytope, the natural measure is taken in its affine hull. A simplex with vertices has volume
This formula connects volume with the determinant. General polytopes can be triangulated into simplices with disjoint interiors, reducing volume and integration problems to finite sums. A triangulation using only the original vertices always exists, although allowing additional points may produce subdivisions with different computational advantages.
Volumes of Minkowski sums exhibit polynomial behavior. For convex polytopes and nonnegative real numbers , the expression
is a homogeneous polynomial of degree in and . Its coefficients are mixed volumes, which measure interactions between the shapes rather than only their separate sizes. In dimension two, this becomes a quadratic formula involving the two areas and a mixed-area term. Mixed volumes connect convex geometry with inequalities and with the counting of solutions to systems of polynomial equations.
A lattice polytope has all its vertices in , linking polytope theory with number theory. For a lattice polytope , the Ehrhart polynomial counts integer points in dilations:
For a full-dimensional lattice polytope, this is a polynomial of degree , with leading coefficient equal to its Euclidean volume and constant term . For the unit cube,
If the vertices have rational rather than integer coordinates, the counting function is generally a quasipolynomial: its coefficients vary periodically with .
Ehrhart reciprocity relates boundary and interior counts:
for positive integers , with relative interior used when working in the polytope’s affine span. In two dimensions, Pick’s theorem gives the particularly simple identity
where and count interior and boundary lattice points.
Lattice polytopes also appear in algebraic geometry. Under standard constructions, their integer points specify monomials and associated projective toric varieties. The normal fan of a polytope records which faces maximize a linear functional in each direction. When the polytope is rational, this fan supplies algebraic data, translating questions about geometry into questions about monomials, cones, and graded rings.
Optimization and computational complexity
A bounded linear programming problem seeks to maximize or minimize a linear functional over a polytope:
If the feasible polytope is nonempty, an optimum exists and at least one vertex is optimal. More precisely, all optimal points form a face, which may be a single vertex, an edge, or a higher-dimensional region. This geometric fact explains why vertices are central even when the original problem has continuously varying variables.
The simplex method moves among basic feasible solutions, usually interpreted as vertices joined by edges. A pivot changes the active constraints and seeks improvement in the objective. Degeneracy complicates this picture: several bases may represent the same vertex, and a pivot may change the basis without changing the point. Although simplex algorithms are often effective in practice, particular pivot rules have exponential worst-case examples. Polynomial-time solvability of linear programming was established by Leonid Khachiyan’s ellipsoid-method result in 1979; Narendra Karmarkar’s 1984 work helped launch modern interior-point methods.
Graph diameter measures the number of edge steps needed between vertices and therefore has a natural connection to simplex-type algorithms. The Hirsch conjecture proposed that a -polytope with facets has graph diameter at most . Francisco Santos constructed a counterexample in 2010. Its failure does not settle all algorithmic questions about pivot paths: a short path need not improve a particular objective at every step, and an algorithm may not know how to find the shortest one.
In integer programming, the feasible points are restricted to integer coordinates. If the feasible set is bounded, their convex hull is another polytope, called the integer hull. Linear optimization over that hull gives the same optimal value as the original integer problem, but the hull may require many more inequalities than the initial relaxation. Cutting-plane methods add inequalities valid for integer solutions, while branch-and-bound methods divide the search into smaller subproblems. The central difficulty is often discovering enough of the integer hull’s geometry without constructing it completely.
Representation conversion and enumeration are separate computational challenges. Given vertices, one may seek all facets; given inequalities, one may seek all vertices. Output size can itself be exponential, so complexity must account for both input and output. Exact rational arithmetic can certify incidences, whereas floating-point implementations require care near degeneracies, where nearly coincident hyperplanes or nearly dependent coordinates can produce incorrect combinatorial decisions.
Extended formulations offer another strategy. Instead of describing directly, an algorithm describes a higher-dimensional polyhedron whose projection is . The smallest possible inequality count is a measure of extension complexity. Some structured polytopes admit compact extensions, while others provably require exponentially many inequalities even after auxiliary variables are introduced.
Realization problems and generalized polytopes
A realization problem asks whether specified combinatorial data can occur as the face structure of a convex polytope. In dimension two, every finite cycle with at least three vertices is realized by a convex polygon. In dimension three, Steinitz’s theorem reduces the problem for graphs to planarity and three-vertex-connectivity. Higher dimensions are substantially less restrictive in some respects and much more complicated in others: combinatorial structures may satisfy many necessary conditions yet admit no convex realization.
A realization space records all coordinate realizations of a fixed combinatorial type, usually after an appropriate normalization. These spaces need not resemble a single uncomplicated region. Universality results show that realization spaces of four-dimensional polytopes can encode extremely complicated algebraic and topological behavior. Consequently, determining whether a combinatorial type is realizable is connected with solving systems of polynomial equations and inequalities over the real numbers, rather than merely assembling plausible local pieces.
Coordinate arithmetic adds another layer. Some combinatorial types admit rational-coordinate realizations, while others force irrational coordinates. Thus the existence of a real realization does not guarantee the existence of one using only rational numbers. A transformation that preserves incidences may simplify coordinates, but it cannot always eliminate the arithmetic obstruction. Realizability and rational realizability are therefore distinct questions.
An oriented matroid abstracts sign information describing orientations and sidedness in vector or point configurations. For example, signs of appropriate determinants record which ordered point sets have positive orientation, negative orientation, or affine dependence. Such information constrains possible faces and separating hyperplanes. Some oriented matroids arise from real coordinate configurations and others do not, providing a framework in which geometric realizability can be studied independently of a particular coordinate list.
An abstract polytope replaces a geometric solid by a ranked partially ordered set satisfying incidence and connectivity axioms. Its elements are interpreted as faces, and maximal chains are flags. The axioms capture important local properties of ordinary polytopes, including the requirement that exactly two intermediate faces occur in certain rank-two intervals. Abstract polytopes need not be face lattices of convex Euclidean polytopes, and their automorphism groups can be studied without first finding a spatial embedding.
Nonconvex and star polytopes provide a different generalization. Their faces may intersect in ways excluded by convexity, and a drawing can obscure whether crossings count as incidences. Precise definitions must therefore specify the underlying face structure and geometric realization. Infinite analogues, often called apeirotopes, extend the subject further, but lie outside the finite convex-hull definition used in convex geometry.
Applications across mathematics and science
Polytopes provide finite models for constrained distributions. The set of probability vectors with possible outcomes is the standard simplex
Its vertices represent distributions concentrated on a single outcome. Linear constraints on probabilities cut out smaller polytopes, so feasibility questions involving marginal totals or moment conditions become geometric questions. A linear expected value is optimized at a vertex, although nonlinear quantities such as entropy may attain their optimum in the interior.
Transportation polytopes consist of nonnegative matrices with prescribed row and column sums. A particularly important example is the Birkhoff polytope of doubly stochastic matrices. The Birkhoff–von Neumann theorem states that it is the convex hull of permutation matrices. Thus every doubly stochastic matrix can be expressed as a convex combination of discrete assignments. This result links continuous optimization with matching and allocation problems, and illustrates how a polytope can encode a finite set of combinatorial choices through its vertices.
Many discrete optimization problems use the same principle. The traveling-salesman polytope is the convex hull of incidence vectors of tours, while matching and cut polytopes encode selected edges of graphs. A tour can be represented by a zero-one vector, but its convex hull generally has a much richer inequality structure than the elementary constraints defining an initial relaxation. Polyhedral analysis identifies valid inequalities, describes special classes of instances, and studies the limits of compact linear descriptions.
In numerical computation, polytopes serve as domains and mesh cells. A triangulation of a polygonal or polyhedral region supports piecewise-polynomial approximation in the finite element method. Barycentric coordinates on simplices provide local basis functions and interpolation rules. More general polyhedral meshes require additional constructions, but retain the advantage of representing complicated domains by finitely many flat-sided cells. Convex hulls and half-space intersections are also basic operations in collision detection and geometric modeling.
In game theory, a player’s mixed strategy lies in a simplex. For finite zero-sum games, equilibrium computation can be formulated as paired linear programs, with feasible polytopes representing probability choices and guaranteed payoffs. This is a particularly direct instance of geometry translating strategic conditions into inequalities.
Related structures occur in physics and algebra. Convex sets of correlations in finite classical models can form polytopes whose facets express limiting inequalities. Newton polytopes record exponent vectors of nonzero terms in a polynomial, retaining geometric information about multiplication and systems of equations. In these uses, the polytope does not merely illustrate a problem: its face structure, projections, and arithmetic properties organize the underlying analysis.
Historical development
The earliest systematic study concerned polygons and three-dimensional solids rather than arbitrary-dimensional objects. Book XIII of Euclid’s *Elements* constructs the five regular convex solids and establishes their classification within the classical setting. Archimedes studied semiregular solids, known through later accounts of his work. These investigations emphasized lengths, angles, construction, and symmetry, laying foundations for the later distinction between geometric shape and combinatorial incidence.
The eighteenth century brought a decisive counting perspective. Leonhard Euler investigated the relation between vertices, edges, and faces, giving the formula now written for convex polyhedra. Subsequent work clarified its hypotheses and connected it with topology. In 1813, Augustin-Louis Cauchy proved his rigidity theorem: convex polyhedra with the same combinatorial structure and congruent corresponding faces are congruent. The convexity assumption is crucial, and the theorem helped distinguish incidence, local metric data, and global shape as separate aspects of polyhedral geometry.
Higher-dimensional regular polytopes were systematically investigated in the nineteenth century. Ludwig Schläfli developed their classification in the 1850s, including the exceptional regular polytopes in four dimensions. His work established that higher-dimensional analogues were mathematically structured objects, even when ordinary spatial visualization was unavailable. Later treatments, notably those of H. S. M. Coxeter, organized regular polytopes through reflection groups and systematic notation for their face and symmetry structures.
A parallel development replaced highly symmetric examples with general convex bodies and inequalities. Hermann Minkowski’s work on convex geometry, support functions, and the geometry of numbers was especially influential. It connected the shape of convex sets with arithmetic and linear structure. Ernst Steinitz’s early twentieth-century research, including his characterization of three-dimensional polytope graphs, made combinatorial realization a central theme rather than a subsidiary question about drawing solids.
The growth of linear programming after George Dantzig’s introduction of the simplex method in 1947 gave polytope theory an extensive computational role. George B. Dantzig’s optimization framework and later work on polyhedral combinatorics showed that vertices, facets, and projections could encode practical decision problems as well as classical geometry. Branko Grünbaum’s Convex Polytopes, first published in 1967, helped consolidate the modern field around its geometric and combinatorial foundations.
Later developments diversified the subject further. Extremal face-count theorems connected it with commutative algebra and algebraic geometry; universality theorems revealed the complexity of realization spaces; and optimization introduced questions about efficient descriptions, pivot rules, and extension complexity. Each direction retained the same finite geometric core while drawing on a different kind of structure: incidence, metric geometry, arithmetic, symmetry, or computation.