Convex polytope
A convex polytope is a bounded subset of Euclidean space \mathbb{R}^d that can be defined either as the convex hull of a finite set of points or as the intersection of a finite number of half-spaces, with these two representations being equivalent in finite dimensions.[1][2] This structure ensures that the polytope is convex, meaning the line segment between any two points in the set lies entirely within it, and it possesses a finite number of extreme points (vertices), edges, faces, and higher-dimensional facets.[3] Convex polytopes generalize familiar shapes such as polygons in two dimensions and polyhedra in three dimensions, where the latter include regular forms like the Platonic solids.[4] The combinatorial structure of convex polytopes is described by their face lattice, which enumerates vertices, edges, faces, and facets, satisfying relations like Euler's formula V - E + F = 2 for three-dimensional polyhedra, where V, E, and F denote the numbers of vertices, edges, and faces, respectively.[5] Notable examples include the d-simplex (with d+1 vertices), the hypercube (with $2^d vertices), and the cross-polytope (dual to the hypercube).[6] These objects exhibit rich geometric properties, such as being simple (each vertex incident to exactly d edges) or simplicial (each facet a simplex), which influence their enumeration and decomposition.[4] The study of convex polytopes traces back to antiquity, with early investigations into regular polyhedra by ancient Greek mathematicians, and saw significant modern development in the mid-20th century through works on combinatorial and geometric aspects.[2] Branko Grünbaum's 1967 monograph Convex Polytopes provided a foundational treatment of their combinatorial theory, inspiring advances in face enumeration and upper bound theorems.[4] Today, convex polytopes are pivotal in fields like linear programming, where optimization problems are solved over polyhedral feasible regions, and in algebraic geometry, where they underlie toric varieties and Ehrhart theory for counting lattice points.[5] Their applications extend to computer science, including algorithms for polytope representation conversion between vertex and half-space descriptions.[5]History
Early developments
The study of convex polytopes originated in classical geometry with investigations into three-dimensional polyhedra, which served as precursors to the more general concept of polytopes. Around 250 BCE, Archimedes enumerated the thirteen semi-regular polyhedra, now known as Archimedean solids, in a now-lost treatise referenced by Pappus of Alexandria; these uniform polyhedra, with regular polygonal faces and identical vertex configurations, highlighted early combinatorial and geometric properties of convex bounded polyhedra in Euclidean space.[7] A significant combinatorial advancement came in the 18th century with Leonhard Euler's 1752 publication of his polyhedron formula, which relates the vertices V, edges E, and faces F of a convex polyhedron by V - E + F = 2; this relation provided an early topological invariant applicable to convex polyhedra and foreshadowed broader insights into polytope structure.[8] In 1794, Adrien-Marie Legendre contributed to the understanding of polyhedral volumes in his Éléments de géométrie, where he presented an independent proof of Euler's formula and developed methods for computing volumes of polyhedra through triangulation into pyramids and tetrahedra, emphasizing the role of convexity in ensuring decomposition without overlaps or gaps.[9] During the 19th century, Augustin-Louis Cauchy and Jakob Steiner advanced the theory of convex bodies, including polytopes, by focusing on their geometric properties and decompositions. In 1813, Cauchy demonstrated that the dihedral angles of a convex polyhedron are uniquely determined by its facial structure, establishing a rigidity theorem that underscored convexity as essential for structural integrity.[10] Steiner, in works from the 1840s, introduced symmetrization techniques and the parallel body formula, which decomposes the volume of a convex body's offset into intrinsic measures, further solidifying convexity as a foundational property for analyzing shapes and their transformations. These efforts laid the groundwork for treating convex bodies as decomposable into simpler convex components, influencing subsequent geometric studies.[11]20th-century advancements
In the late 19th and early 20th centuries, Hermann Minkowski laid foundational work for abstract convex polytopes in higher dimensions through his development of the geometry of numbers. In his 1896 book Geometrie der Zahlen, Minkowski formalized the convex hull as the smallest convex set containing a given set of points, extending this concept rigorously to n-dimensional Euclidean space and emphasizing its role in bounding lattice points within convex bodies. He further established Minkowski's theorem on lattice polytopes, stating that any convex body in \mathbb{R}^d that is symmetric about the origin and has volume greater than $2^d must contain a non-zero lattice point in its interior or boundary. This theorem provided essential tools for understanding the distribution of lattice points in n-dimensional convex sets, bridging number theory and convex geometry. Building on these ideas, advancements in the theory of volumes for convex bodies emerged in the mid-20th century. Mixed volumes generalize the notion of volume for sums of convex bodies, and their role in the Brunn-Minkowski inequality, originally proved by Minkowski in 1896 for convex bodies, which asserts that for non-empty compact convex subsets K, L \subset \mathbb{R}^d, the volume satisfies |K + L|^{1/d} \geq |K|^{1/d} + |L|^{1/d}, with equality if and only if K and L are homothetic. This inequality underscored the subadditivity of volumes under Minkowski summation and became a cornerstone for asymptotic geometric analysis in n dimensions.[5] In 1967, Branko Grünbaum published his seminal monograph Convex Polytopes, which provided a comprehensive foundational treatment of their combinatorial theory, including detailed studies on face lattices, realizations of combinatorial types, and inequalities for face numbers. This work inspired significant advances, such as the upper bound theorem and efforts toward classifying polytopes.[4] In the 1970s, Peter McMullen advanced the combinatorial structure of convex polytopes by formalizing the face lattice and its associated invariants. The face lattice of a convex polytope encodes the inclusion relations among its faces, from vertices to the full polytope itself, providing a poset structure that captures the topology and combinatorics in higher dimensions.[12] McMullen's 1970 upper bound theorem determined the maximum number of k-faces for a d-dimensional polytope with v vertices, achieved by cyclic polytopes, and relied on the f-vector (f_0, f_1, \dots, f_{d-1}), where f_i counts the i-dimensional faces.[12] For simplicial polytopes, he incorporated the Dehn-Sommerville relations, which impose linear equations on the f-vector such as \sum_{i=0}^d (-1)^i f_i = 0 (Euler's formula generalized), linking face counts across dimensions and enabling the g-theorem's characterization of possible f-vectors. The Schläfli symbol, introduced by Ludwig Schläfli in 1852, saw significant generalization and application to higher-dimensional regular polytopes during the 20th century, particularly through enumerative and symmetry studies. The symbol \{p_1, p_2, \dots, p_{n-1}\} recursively describes regular polytopes where each entry specifies the number of facets meeting at lower-dimensional elements, naturally extending to n dimensions beyond the classical Platonic solids.[13] In four dimensions, Schläfli identified six regular 4-polytopes (Schläfli polytopes), including the 5-cell \{3,3,3\}, 8-cell \{4,3,3\}, 16-cell \{3,3,4\}, 24-cell \{3,4,3\}, 120-cell \{5,3,3\}, and 600-cell \{3,3,5\}, whose constructions and symmetry groups were further explored in works like H.S.M. Coxeter's 1948 analysis, confirming no additional regular 4-polytopes exist. These developments highlighted that in each dimension greater than 4, there are exactly three regular convex polytopes: the regular simplex, the hypercube, and the cross-polytope.Definitions and Basic Concepts
Core definition
A convex polytope is a fundamental object in convex geometry, defined as the convex hull of a finite set of points in Euclidean space \mathbb{R}^d.[1] This construction captures bounded regions with flat faces, such as polygons in two dimensions or polyhedra in three dimensions.[4] Formally, given a finite set V = \{v_1, \dots, v_n\} \subset \mathbb{R}^d, the convex polytope P is P = \operatorname{conv}(V), where the convex hull operator is defined as \operatorname{conv}(V) = \left\{ \sum_{i=1}^n \lambda_i v_i \;\middle|\; \lambda_i \geq 0 \ \forall i, \ \sum_{i=1}^n \lambda_i = 1, \ v_i \in V \right\}. [2] This set consists of all possible convex combinations of the points in V, ensuring that P is the smallest convex set containing V.[4] A key property of a convex polytope is its convexity: for any two points x, y \in P, the entire line segment connecting them, parameterized as (1-t)x + t y for t \in [0,1], lies within P.[1] Equivalently, a convex polytope can be realized as the bounded intersection of finitely many half-spaces in \mathbb{R}^d.[1] In distinction from general convex sets, which may be unbounded or possess infinitely many extreme points, convex polytopes are compact (closed and bounded) and have only finitely many extreme points (vertices), which are a subset of the generating set V.[4]Bounded versus unbounded polytopes
In convex geometry, bounded polytopes are compact convex sets that have finite extent in every direction, meaning they are closed and bounded in Euclidean space. These polytopes are equivalently characterized as the convex hull of a finite number of points, a property that ensures they possess only finitely many vertices, edges, and faces.[14] Unbounded polyhedra, on the other hand, arise as intersections of finitely many half-spaces that do not result in a bounded set, allowing infinite extension in certain directions. A key structural feature of such unbounded polyhedra is their recession cone, which consists of all directions along which the polyhedron remains invariant under translation, effectively describing the unbounded rays emanating from any point within it.[15] For instance, a single half-space in \mathbb{R}^d, defined by a linear inequality such as \{x \in \mathbb{R}^d \mid a^\top x \leq b\}, serves as a classic example of an unbounded polyhedron, where the recession cone is the set \{d \mid a^\top d \leq 0\}.[15] Regarding terminology, the word "polytope" is frequently reserved for bounded cases in modern literature, distinguishing them from the broader class of convex polyhedra that may be unbounded; this convention is particularly prevalent in optimization contexts like linear programming, where unbounded feasible regions are common.[14]Representations
Vertex-based representation
A convex polytope P in \mathbb{R}^d admits a vertex-based representation, or V-representation, as the convex hull of a finite set of points known as its vertices or extreme points: P = \conv\{ v_1, \dots, v_n \} \subseteq \mathbb{R}^d, where each v_i is a point in \mathbb{R}^d and n is finite.[2] This formulation defines P directly from its boundary-generating elements, with the vertices forming the minimal set whose convex combinations yield all points in P.[16] The extreme points theorem characterizes this representation precisely for polytopes. Every point in P can be expressed as a convex combination of the vertices, and no vertex itself is a nontrivial convex combination of the other points in P.[17] This follows from the compactness and convexity of P, ensuring that the vertices are exactly the extreme points, and distinguishes polytopes from more general convex sets by their finite extremal structure.[18] Consequently, the V-representation provides a complete and non-redundant description of P via its n vertices. This approach offers advantages in scenarios requiring generation from discrete points, such as approximating shapes from sampled data. It is intuitive for computational purposes, facilitating direct manipulation of boundary points without implicit constraints. In computer graphics, vertex representations enable efficient modeling and rendering of polyhedral objects by specifying coordinates for vertices, edges, and faces.[19] In optimization, it supports tasks like vertex enumeration for solving linear programs over polytopes or computing minimal-norm points within simplices derived from vertices.[20] A fundamental invariant in this context is f_0(P), the number of vertices, which quantifies the combinatorial complexity of P and influences algorithms for polytope manipulation. This V-representation is equivalent to the half-space form in fully describing bounded convex sets but emphasizes generative points over bounding inequalities.Half-space representation
A convex polytope P in \mathbb{R}^d admits a half-space representation as the intersection of a finite number of closed half-spaces, expressed as P = \{ x \in \mathbb{R}^d \mid A x \leq b \}, where A is an m \times d real matrix and b is a real vector in \mathbb{R}^m, with m finite.[21] This formulation captures the polytope as the solution set to a system of linear inequalities, each defining a bounding half-space.[21] Each row a_i^\top of A, paired with the corresponding entry b_i of b, specifies a supporting hyperplane \{ x \mid a_i^\top x = b_i \}, with the half-space \{ x \mid a_i^\top x \leq b_i \} containing P.[21] The facets of P, which are the (d-1)-dimensional faces, arise from the inequalities that are tight (i.e., active) for some points in P, meaning equality holds on those facets while the polytope lies strictly on one side of the hyperplane.[21] Redundant inequalities, which do not contribute new facets, may be present but can be eliminated to obtain a minimal representation.[21] This half-space representation is advantageous in optimization contexts, where polytopes often model feasible regions defined by linear constraints, as in linear programming problems. It provides a dual perspective to the vertex-based convex hull description, facilitating conversions between representations for computational purposes.[21] For P to be bounded (a polytope rather than an unbounded polyhedron), the representation must ensure no nonzero recession direction exists; specifically, the recession cone \{ x \mid A x \leq 0 \} must be trivial, containing only the origin.[21] A common normalization assumes the origin lies in the interior of P, which implies strict feasibility of the inequalities and guarantees boundedness when the recession cone condition holds.[21]Equivalence between representations
A fundamental result in polyhedral theory establishes the equivalence between the vertex and half-space representations for convex polytopes. Specifically, every bounded convex polytope in \mathbb{R}^d can be expressed both as the convex hull of a finite set of vertices V = \{v_1, \dots, v_k\}, denoted \operatorname{conv}(V), and as the intersection of finitely many half-spaces \{x \in \mathbb{R}^d \mid A x \leq b\}, where A is an m \times d matrix and b \in \mathbb{R}^m. This is known as the Minkowski–Weyl theorem. The vertices in the half-space representation \{x \mid A x \leq b\} correspond precisely to the basic feasible solutions of the linear system, obtained by solving subsystems of d linearly independent tight inequalities A_I x = b_I, where I is a subset of d rows of (A, b) with full rank. A proof sketch of the theorem utilizes Farkas' lemma, which characterizes the feasibility of linear inequalities via alternatives. To show that a vertex representation yields a half-space one, consider the boundedness implying compactness; the supporting hyperplanes at extreme points generate the finite inequalities defining the polytope. Conversely, the finite intersection ensures the feasible region has finitely many extreme points, recoverable as solutions to the tight systems above, with Farkas' lemma guaranteeing no unbounded rays in the bounded case.[22] This equivalence has key implications: it guarantees the existence of conversion algorithms between representations, such as double description methods that enumerate vertices from facets or vice versa, enabling computational verification and manipulation of polytopes. For unbounded polyhedra, the equivalence extends if the recession cone—capturing the directions of unboundedness—is polyhedral, i.e., finitely generated as a conical hull of extreme rays.Support function representation
The support function of a convex polytope P \subset \mathbb{R}^d provides a functional representation defined by h_P(u) = \sup \{ \langle x, u \rangle \mid x \in P \} for all directions u \in \mathbb{R}^d, where \langle \cdot, \cdot \rangle denotes the standard inner product.[21] Since P is compact, the supremum is attained and equals the maximum inner product. This function fully determines the polytope, as P = \{ x \in \mathbb{R}^d \mid \langle x, u \rangle \leq h_P(u) \ \forall \, u \in \mathbb{R}^d \}. The support function h_P is convex, as it arises as the pointwise supremum of linear functions, and positively homogeneous of degree one, satisfying h_P(\lambda u) = \lambda h_P(u) for all \lambda \geq 0 and u \in \mathbb{R}^d. For a polytope with finitely many vertices v_1, \dots, v_m, it takes the explicit form h_P(u) = \max_{i=1}^m \langle v_i, u \rangle, which renders h_P piecewise linear, with linear pieces corresponding to the normal cones at the vertices.[21] This representation offers computational advantages in geometric operations. Notably, the support function of the Minkowski sum of two polytopes P and Q satisfies h_{P+Q}(u) = h_P(u) + h_Q(u) for all u \in \mathbb{R}^d, simplifying the analysis of sums without enumerating vertices or facets. Similarly, it facilitates the study of polarity, where the polar dual P^\circ = \{ y \in \mathbb{R}^d \mid \langle y, x \rangle \leq 1 \ \forall \, x \in P \} admits a description in terms of the reciprocal behavior of h_P, aiding duality transformations in convex geometry.Examples
Low-dimensional cases
In one dimension, a convex polytope is simply the convex hull of two distinct points, forming a closed line segment.[1] In two dimensions, convex polytopes are known as convex polygons, which are planar figures bounded by a finite chain of line segments such that no internal angle exceeds 180 degrees and all line segments lie on the boundary. A basic example is the triangle, a convex polygon with 3 vertices and 3 edges. Another simple case is the quadrilateral, featuring 4 vertices and 4 edges. Regular convex polygons, such as the pentagon with 5 equal sides and angles, illustrate symmetric cases where all vertices lie on a common circle.[23] In three dimensions, convex polytopes take the form of convex polyhedra, bounded solids with flat polygonal faces, straight edges, and vertices. Prominent examples are the five Platonic solids, which are regular convex polyhedra with identical regular polygonal faces meeting the same number of times at each vertex: the tetrahedron (4 triangular faces), cube (6 square faces, 8 vertices, 12 edges), octahedron (8 triangular faces), dodecahedron (12 pentagonal faces), and icosahedron (20 triangular faces).[24] Beyond these, the 13 Archimedean solids represent convex polyhedra composed of regular polygons of two or more types, arranged with identical vertex configurations, such as the truncated tetrahedron or cuboctahedron.[25] A fundamental relation for convex polyhedra that are topologically equivalent to a sphere is Euler's polyhedral formula:V - E + F = 2,
where V is the number of vertices, E the number of edges, and F the number of faces; for instance, the cube satisfies $8 - 12 + 6 = 2.[26]