# Polytope
A polytope is a geometric object bounded by portions of lines, planes, or hyperplanes: in two dimensions it is a polygon, in three a polyhedron, and in general a bounded region of n-dimensional space enclosed by finitely many hyperplanes[1](https://mathworld.wolfram.com/Polytope.html). The modern convex theory centers on a single object with two equivalent descriptions, and the word itself was introduced in the context of four-dimensional geometry by Alicia Boole Stott (1860–1940), daughter of the logician [George Boole](https://www.edgepedia.org/george-boole)[1](https://mathworld.wolfram.com/Polytope.html) • [2](https://mathshistory.st-andrews.ac.uk/Biographies/Stott/).
| Key fact | Detail |
|---|---|
| Definition | A polytope is a bounded polyhedron, equivalently the convex hull of a finite set of points; the two descriptions are a classical theorem[3](https://math.mit.edu/~goemans/18433S13/polyhedral.pdf) • [4](https://math.mit.edu/~rstan/transparencies/polytopes.pdf) |
| Origin of the word | Introduced by Alicia Boole Stott to describe a four-dimensional convex solid[2](https://mathshistory.st-andrews.ac.uk/Biographies/Stott/) |
| Regular polytopes | Ludwig Schläfli classified them around 1850: six types in dimension 4, three in every dimension 5 and higher[1](https://mathworld.wolfram.com/Polytope.html) • [5](https://www.ams.org/journals/notices/201805/201805FullIssue.pdf) |
| Central algorithmic problem | Vertex enumeration (computing vertices from halfspaces) and facet enumeration are equivalent under duality; whether either can be solved in time polynomial in |H| + |V| and the dimension is open[6](https://www.sciencedirect.com/science/article/pii/S0925772196000235) |
| Extension complexity | The minimum number of facets of a higher-dimensional polytope that projects onto P; by Yannakakis's theorem it equals the nonnegative rank of the slack matrix[7](https://wiki.siam.org/siag-op/images/siag-op/9/90/ViewsAndNews-25-1.pdf) |
| Optimization role | A linear program's feasible set is a convex polyhedron, possibly unbounded; a bounded polyhedron is a polytope. On a nonempty polytope, a linear objective attains an optimum at a vertex, and multiple optima form an optimal face that may have dimension greater than one. A general linear program need not have an optimum or any vertices[8](https://technav.ieee.org/topic/linear-programming/) • [24](https://courses.csail.mit.edu/6.854/19/Scribe/s12-duality/s12-duality.html) |
| Landmark monograph | Branko Grünbaum's *Convex Polytopes* (1967) shaped polytope theory as known today[5](https://www.ams.org/journals/notices/201805/201805FullIssue.pdf) |
## Definition and representations
In the standard convex setting, a polyhedron in \( \mathbb{R}^n \) is the intersection of finitely many halfspaces, \( P = \{x \in \mathbb{R}^n : Ax \le b\} \), and a polytope is a bounded polyhedron[3](https://math.mit.edu/~goemans/18433S13/polyhedral.pdf). A halfspace is a set of the form \( \{x : a^{\mathrm{T}}x \le b\} \)[3](https://math.mit.edu/~goemans/18433S13/polyhedral.pdf). The same objects admit a dual description: a classical theorem states that a set is a bounded intersection of halfspaces if and only if it is the convex hull \( \mathrm{conv}(X) \) of some finite set \( X \)[4](https://math.mit.edu/~rstan/transparencies/polytopes.pdf). These are called the H-representation (halfspaces) and V-representation (vertices) of the polytope[6](https://www.sciencedirect.com/science/article/pii/S0925772196000235).
The equivalence of the two descriptions is not obvious; one direction can be shown by repeatedly applying Fourier–Motzkin elimination to eliminate the convex-combination variables and keep only the original coordinates[3](https://math.mit.edu/~goemans/18433S13/polyhedral.pdf). A d-dimensional polytope can also be specified algebraically as the solution set of a system \( mx \le b \), where m is a real s × d matrix and b a real s-vector[1](https://mathworld.wolfram.com/Polytope.html).
The part of a polytope lying in one of its bounding hyperplanes is called a cell[1](https://mathworld.wolfram.com/Polytope.html). A simple polytope is a d-dimensional convex polytope with exactly d edges incident with each vertex; every convex polygon is simple[9](https://mathworld.wolfram.com/SimplePolytope.html). Named families studied for their own combinatorial structure include the order polytope of a finite partially ordered set, whose vertices are the indicator vectors of upward-closed subsets[10](https://mathworld.wolfram.com/OrderPolytope.html), and the [Birkhoff polytope](https://www.edgepedia.org/birkhoff-polytope) of n × n doubly stochastic matrices[11](https://mathworld.wolfram.com/BirkhoffPolytope.html).
## History and regular polytopes
Three-dimensional work goes back to antiquity: the Platonic solids, and the thirteen Archimedean solids described by [Archimedes](https://www.edgepedia.org/archimedes) around 250 BC, whose faces are regular but not all alike. Serious consideration of higher-dimensional geometric objects appeared only in the second half of the nineteenth century, as classical geometry developed toward projective and non-[Euclidean geometry](https://www.edgepedia.org/euclidean-geometry)[12](https://www.polytope.de/hist.html).
The Swiss mathematician Ludwig Schläfli (1814–1895) produced by 1852 a manuscript classifying the regular polytopes in all dimensions, work rejected by the academy in Vienna for its length and not published until 1901[13](https://www.ams.org/journals/notices/201911/rnoti-p1853.pdf). A regular n-dimensional polytope, for n > 2, is one whose cells are regular (n − 1)-dimensional polytopes, also regular at each vertex[13](https://www.ams.org/journals/notices/201911/rnoti-p1853.pdf). In every dimension above three the classification yields three types: the n-simplex having n + 1 cells, the n-cube having 2n cells, and the orthoplex having \( 2^{n} \) cells; when n ≥ 5 no regular polytopes exist beyond these, but dimension four contains precisely three additional ones—the 24-cell, the 120-cell, and the 600-cell—with octahedra, dodecahedra, and tetrahedra as their cells[13](https://www.ams.org/journals/notices/201911/rnoti-p1853.pdf). Dimension four is the exceptional case, with six regular polytopes, one more than dimension three[5](https://www.ams.org/journals/notices/201805/201805FullIssue.pdf).
**Alicia Boole Stott.** With no formal mathematical education, Boole Stott developed at about age eighteen an intimate grasp of four-dimensional geometry using wooden cubes supplied by her brother-in-law Charles Howard Hinton. She found the six regular four-dimensional polytopes, bounded by 5, 16, or 600 tetrahedra, 8 cubes, 24 octahedra, or 120 dodecahedra, and computed their three-dimensional sections by purely Euclidean constructions, making cardboard models of them[2](https://mathshistory.st-andrews.ac.uk/Biographies/Stott/). A collaboration with the [Groningen](https://www.edgepedia.org/groningen) geometer Pieter Hendrik Schoute lasted almost twenty years and led her to publish; the [University of Groningen](https://www.edgepedia.org/university-of-groningen) awarded her an honorary doctorate in 1914[2](https://mathshistory.st-andrews.ac.uk/Biographies/Stott/) • [14](https://doi.org/10.1007/s40329-014-0065-x). In later life she worked with H. S. M. Coxeter, whose book *Regular Polytopes* records much of her biography[2](https://mathshistory.st-andrews.ac.uk/Biographies/Stott/).
Modern polytope theory was largely shaped by Grünbaum's 1967 monograph *Convex Polytopes*, which presented Steinitz's theorem in its current form: a graph is realizable as the vertex-edge graph of a three-dimensional polytope if and only if it is planar and 3-connected[5](https://www.ams.org/journals/notices/201805/201805FullIssue.pdf).
## Computing vertices and facets
Switching between the V- and H-representations defines the two central computational problems of polytope theory. The [vertex enumeration problem](https://www.edgepedia.org/vertex-enumeration-problem) computes the vertex set V from the halfspace set H; the facet enumeration problem computes H from V. The two are essentially equivalent under point/hyperplane duality[6](https://www.sciencedirect.com/science/article/pii/S0925772196000235).
No total polynomial-time algorithm, one whose running time is polynomial in both input and output size, is known for either problem in general dimension[15](https://arxiv.org/abs/1412.3987). The difficulty is partly intrinsic to the output: by the upper bound theorem, the number of faces of a convex polytope can be exponential in the worst case[15](https://arxiv.org/abs/1412.3987). David Avis, David Bremner, and Raimund Seidel showed that every main known class of [convex hull algorithms](https://www.edgepedia.org/convex-hull-algorithms) has at least one of two weaknesses, poor handling of degeneracies or poor control of intermediate result sizes, and constructed families of polytopes, fat-lattice or intricate polytopes for the first weakness and dwarfed polytopes for the second, on which the algorithms run in superpolynomial time[6](https://www.sciencedirect.com/science/article/pii/S0925772196000235).
Total polynomial-time algorithms do exist for restricted inputs. A pivoting algorithm solves vertex enumeration for simple polytopes and convex hull for simplicial polytopes in total polynomial time, and a total polynomial-time vertex enumeration algorithm is known for 0/1-polytopes, whose vertices have only 0 and 1 coordinates[15](https://arxiv.org/abs/1412.3987). A 2014 result gives a total polynomial-time algorithm for polytopes whose associated linear matroid has branch-width bounded by a constant[16](https://arxiv.org/abs/1404.5584), and a first total polynomial-time algorithm computes the edge-skeleton, including the vertices, of a polytope given by an optimization or separation oracle together with a superset of its edge directions[15](https://arxiv.org/abs/1412.3987). Approximate vertex enumeration, which asks for the vertices of a polytope close to the given one without requiring combinatorial equivalence, has provably correct algorithms in dimensions 2 and 3 that also tolerate imprecise arithmetic[17](https://jocg.org/index.php/jocg/article/view/3327).
## Extension complexity
A direct linear description of a polytope may require exponentially many inequalities. An extended formulation instead represents P as a linear projection of a higher-dimensional polytope Q with fewer facets, and the extension complexity \( \mathrm{xc}(P) \) is the minimum number of facets in any such formulation[18](https://www.nature.com/nature-index/topics/l4/combinatorial-optimization-and-extension-complexity-of-polytopes). Yannakakis's theorem identifies this quantity with the nonnegative rank of the slack matrix, the matrix recording each vertex's slack with respect to each defining inequality[7](https://wiki.siam.org/siag-op/images/siag-op/9/90/ViewsAndNews-25-1.pdf).
The measure separates easy and hard polytopes sharply. The regular hexagon has extension complexity 5, and the regular n-gons have extension complexity \( O(\log_{2} n) \), a fact used to approximate second-order cone programs by linear programs[7](https://wiki.siam.org/siag-op/images/siag-op/9/90/ViewsAndNews-25-1.pdf). At the other extreme, Rothvoß proved in 2014 that the matching polytope has exponential extension complexity[19](https://arxiv.org/abs/1311.2369), and Göös, Jain, and Watson exhibited an n-node graph whose independent set polytope requires extended formulations of size exponential in \( \Omega(n/\log n) \)[20](https://epubs.siam.org/doi/abs/10.1137/16M109884X). These lower bounds limit how compactly classical combinatorial optimization problems can be expressed as linear programs[18](https://www.nature.com/nature-index/topics/l4/combinatorial-optimization-and-extension-complexity-of-polytopes).
## Polytopes in optimization
The feasible set of a linear program is a convex polyhedron, possibly unbounded, and because both objective and constraints are linear, an optimal solution occurs at a vertex when the feasible set is a nonempty polytope, whereas a general feasible polyhedron need not have vertices or an optimum, and an optimal face may have dimension greater than one[8](https://technav.ieee.org/topic/linear-programming/) • [24](https://courses.csail.mit.edu/6.854/19/Scribe/s12-duality/s12-duality.html). George Dantzig's simplex algorithm, developed in 1947 for U.S. Air Force planning problems, searches these vertices systematically and is counted among the most significant algorithmic contributions of the twentieth century[8](https://technav.ieee.org/topic/linear-programming/).
The geometry of the polytope governs how hard that search can be. The diameter of a polytope, the subject of the Hirsch conjecture, bounds the number of pivot steps any vertex-to-vertex path needs. Kaibel and Kukharenko described in 2024 constructions of extended formulations that establish a relaxed version of the Hirsch conjecture, and showed that if some simplex pivot rule can be bounded by a polynomial in the diameter plus the number of facets, then general linear programming can be solved in strongly polynomial time[21](https://epubs.siam.org/doi/10.1137/23M1585878).
Polytopes also connect to algebraic geometry: every convex polytope with integer vertex coordinates gives rise to a [toric variety](https://www.edgepedia.org/toric-variety)[22](https://math.hse.ru/data/2014/07/02/1309661632/%D1%81%D0%BA.%20toric%20varieties.pdf), and from the viewpoint of the Brunn–Minkowski theory of convex sets, zonotopes, which are sums of line segments, are the simplest objects[23](https://www.sciencedirect.com/topics/mathematics/polytope).
## References
1. [Polytope, Wolfram MathWorld](https://mathworld.wolfram.com/Polytope.html)
2. [Alicia Boole Stott (1860–1940), MacTutor History of Mathematics](https://mathshistory.st-andrews.ac.uk/Biographies/Stott/)
3. [Michel X. Goemans, Linear Programming and Polyhedral Combinatorics, MIT 18.433 lecture notes](https://math.mit.edu/~goemans/18433S13/polyhedral.pdf)
4. [Richard Stanley, Two Poset Polytopes, lecture slides, MIT](https://math.mit.edu/~rstan/transparencies/polytopes.pdf)
5. [Notices of the AMS, May 2018 (Grünbaum and Steinitz's theorem)](https://www.ams.org/journals/notices/201805/201805FullIssue.pdf)
6. [David Avis, David Bremner, Raimund Seidel, How good are convex hull algorithms?, Discrete & Computational Geometry 7 (1997)](https://www.sciencedirect.com/science/article/pii/S0925772196000235)
7. [SIAG/OPT Views and News 25(1), extension complexity and Yannakakis's theorem](https://wiki.siam.org/siag-op/images/siag-op/9/90/ViewsAndNews-25-1.pdf)
8. [Linear Programming, IEEE Technology Navigator](https://technav.ieee.org/topic/linear-programming/)
9. [Simple Polytope, Wolfram MathWorld](https://mathworld.wolfram.com/SimplePolytope.html)
10. [Order Polytope, Wolfram MathWorld](https://mathworld.wolfram.com/OrderPolytope.html)
11. [Birkhoff Polytope, Wolfram MathWorld](https://mathworld.wolfram.com/BirkhoffPolytope.html)
12. [Polytope im 4-Dimensionalen – Historisches, polytope.de](https://www.polytope.de/hist.html)
13. [Regular Polytopes in All Dimensions, Notices of the AMS, November 2019](https://www.ams.org/journals/notices/201911/rnoti-p1853.pdf)
14. [Irene Polo Blanco, Alicia Boole Stott's models of sections of polytopes, Lettera Matematica 2 (2014)](https://doi.org/10.1007/s40329-014-0065-x)
15. [Efficient edge-skeleton computation for polytopes defined by oracles, arXiv:1412.3987](https://arxiv.org/abs/1412.3987)
16. [Polynomial time vertex enumeration of convex polytopes of bounded branch-width, arXiv:1404.5584](https://arxiv.org/abs/1404.5584)
17. [Andreas Löhne, Approximate vertex enumeration, Journal of Computational Geometry 14(1) (2023)](https://jocg.org/index.php/jocg/article/view/3327)
18. [Combinatorial Optimization and Extension Complexity of Polytopes, Nature Index topic summary](https://www.nature.com/nature-index/topics/l4/combinatorial-optimization-and-extension-complexity-of-polytopes)
19. [Sebastian Rothvoß, The matching polytope has exponential extension complexity, arXiv:1311.2369](https://arxiv.org/abs/1311.2369)
20. [Mika Göös, Rahul Jain, Thomas Watson, Extension Complexity of Independent Set Polytopes, SIAM Journal on Computing 47(1) (2018)](https://epubs.siam.org/doi/abs/10.1137/16M109884X)
21. [Volker Kaibel, Kirill Kukharenko, Rock Extensions with Linear Diameters, SIAM Journal on Discrete Mathematics 38(4) (2024)](https://epubs.siam.org/doi/10.1137/23M1585878)
22. [Toric Varieties, lecture notes, HSE](https://math.hse.ru/data/2014/07/02/1309661632/%D1%81%D0%BA.%20toric%20varieties.pdf)
23. [Polytope, an overview, ScienceDirect Topics](https://www.sciencedirect.com/topics/mathematics/polytope)
24. [courses.csail.mit.edu](https://courses.csail.mit.edu/6.854/19/Scribe/s12-duality/s12-duality.html)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Geometry and topology › Metric, convex, and discrete geometry*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license