A convex polyhedron is a region in Euclidean space defined by finitely many linear inequalities. Each inequality specifies a closed half-space, so their intersection is a convex set: the line segment joining any two points of the region lies entirely within it. In classical three-dimensional geometry, the term usually means a bounded solid enclosed by finitely many flat polygonal faces. In optimization and modern convex geometry, it also includes unbounded regions and objects of lower dimension. A bounded convex polyhedron is called a convex polytope.
Definitions and conventions
In , a convex polyhedron has the form
where each is a vector, each is a real number, and the dot denotes the Euclidean dot product. Equivalently,
where is a matrix and the inequality is interpreted componentwise.
For a nonzero vector , the equation defines a hyperplane, and the inequality selects one of its two closed half-spaces. Consequently, a convex polyhedron is always closed, but it need not be bounded.
Terminology depends on context:
- In elementary solid geometry, a convex polyhedron normally has nonempty interior in three dimensions and is bounded.
- In convex analysis and linear programming, polyhedra may be unbounded, empty, or contained in a lower-dimensional affine subspace.
- A polytope is bounded and can have any finite dimension. A three-dimensional convex polytope is the bounded object traditionally called a convex polyhedron.
The word polyhedron also has broader uses for polyhedral surfaces and nonconvex solids. Convexity is therefore an essential qualification, not an automatic property of every object called a polyhedron.
Equivalent representations
Convex polyhedra can be described either by inequalities or by generators.
Half-space representation
The description is called an H-representation. For a cube,
Its six inequalities describe the six supporting planes of its faces.
A representation may contain redundant inequalities: removing one of them may leave the set unchanged. For a full-dimensional polyhedron, a nonredundant inequality description has one inequality for each facet.
Vertex representation
Every nonempty bounded convex polyhedron is the convex hull of finitely many points:
Thus every point can be written as a convex combination
The generating points can be chosen to be exactly the vertices.
For example, the same cube is the convex hull of the eight points .
The Minkowski–Weyl theorem extends this equivalence to unbounded polyhedra. Every nonempty polyhedron can be written as
where
The plus sign means that a point from the first set is added to a point from the second. The vectors describe directions in which the polyhedron extends indefinitely. Opposite directions can represent a complete line, so the theorem also covers polyhedra with no vertices.
Faces, edges, and vertices
A supporting hyperplane meets a convex polyhedron while leaving it entirely on one side. Its intersection with the polyhedron is a face. More generally, a nonempty face can be described as the set of points maximizing a linear functional whose maximum is attained on the polyhedron.
For a full-dimensional three-dimensional convex polyhedron:
- A vertex is a zero-dimensional face.
- An edge is a one-dimensional face.
- A facet, usually simply called a face in elementary geometry, is a two-dimensional face.
In a bounded convex polyhedron, every facet is a convex polygon, every edge belongs to exactly two facets, and at least three edges meet at each vertex. A vertex is an extreme point: it cannot lie strictly between two distinct points of the polyhedron.
The empty face and the whole polyhedron are usually included in the abstract collection of faces. Ordered by containment, the faces form a face lattice, which records incidence relations without specifying lengths or angles.
Two polyhedra may therefore have the same combinatorial structure while having different geometric shapes. A cube and a rectangular box have corresponding vertices, edges, and faces, although their edge lengths may differ.
Euler’s formula and combinatorial structure
For any bounded three-dimensional convex polyhedron, let , , and denote the numbers of vertices, edges, and facets. Then
This is Euler’s polyhedron formula, associated with Leonhard Euler. Its topological explanation is that the boundary is homeomorphic to a sphere, whose Euler characteristic is .
Each face has at least three edges, and each vertex has degree at least three. Counting incidences gives
Together with Euler’s formula, these imply
The first bound is attained precisely when every facet is triangular; the second is attained precisely when exactly three edges meet at every vertex.
The vertices and edges form the polyhedron’s edge graph, an object studied in graph theory. Steinitz’s theorem states that a finite simple graph is the edge graph of a bounded three-dimensional convex polyhedron exactly when it is planar and 3-vertex-connected. Planarity means it can be drawn in the plane without crossing edges; 3-vertex-connectivity means that deleting any two vertices leaves it connected.
Important families
Regular convex polyhedra
There are exactly five Platonic solids, the regular convex polyhedra:
| Solid | Vertices | Edges | Faces | Face shape |
|---|---|---|---|---|
| Tetrahedron | 4 | 6 | 4 | Equilateral triangle |
| Cube | 8 | 12 | 6 | Square |
| Octahedron | 6 | 12 | 8 | Equilateral triangle |
| Dodecahedron | 20 | 30 | 12 | Regular pentagon |
| Icosahedron | 12 | 30 | 20 | Equilateral triangle |
Their regularity requires both regular faces and a uniform arrangement of faces around vertices. Most convex polyhedra have neither property.
Simplicial and simple polyhedra
A bounded three-dimensional convex polyhedron is simplicial if every facet is a triangle. It is simple if exactly three edges meet at every vertex.
The octahedron and icosahedron are simplicial; the cube and dodecahedron are simple. The tetrahedron is both. In dimension , the corresponding definitions require simplex facets and exactly incident edges per vertex.
Prisms and pyramids
A convex prism is obtained by translating a convex polygon into a parallel plane and joining corresponding points. A convex pyramid is the convex hull of a convex polygon and a point outside its plane.
These constructions produce infinite families. Their bases need not be regular, and their side edges need not be perpendicular to the base.
Duality and rigidity
For a bounded full-dimensional convex polyhedron containing the origin in its interior, its polar is
The polar is again a bounded full-dimensional convex polyhedron, and
Polarity reverses face containment. In three dimensions, vertices correspond to facets, edges correspond to edges, and facets correspond to vertices. Thus the cube and octahedron are dual, the dodecahedron and icosahedron are dual, and the tetrahedron is combinatorially self-dual. Simple and simplicial polyhedra are exchanged by duality.
Convexity also imposes strong metric constraints. Cauchy’s rigidity theorem, proved by Augustin-Louis Cauchy in 1813, states that two convex polyhedra with corresponding congruent faces and the same incidence structure are congruent. Informally, a closed convex polyhedral surface cannot flex while its polygonal faces remain rigid. Nonconvex polyhedra do not satisfy the same general rigidity statement.
History
The regular convex polyhedra were studied in ancient Greek mathematics. Book XIII of Euclid’s Elements constructs and compares the five regular solids.
Euler’s eighteenth-century work on vertex, edge, and face counts helped shift attention from individual shapes to general structural properties. Cauchy’s rigidity theorem established a different kind of constraint, linking face geometry to the shape of the entire solid.
During the nineteenth and twentieth centuries, the study of convex bodies, systems of linear inequalities, and higher-dimensional polytopes developed into a unified theory. In the twentieth century, linear programming made polyhedra central objects in mathematical optimization, while Steinitz’s theorem connected three-dimensional convex polyhedra with planar graphs.
Applications and limitations
In mathematical optimization, linear constraints define a polyhedral feasible region. If that region is nonempty and bounded, a linear objective function attains an optimum at a vertex, although an entire edge, face, or the whole region may also be optimal. This fact underlies vertex-based optimization methods.
In integer programming, convex hulls of feasible integer points provide geometric models for discrete problems. Linear inequalities that describe or approximate these hulls support relaxation and cutting-plane methods.
Convex polyhedra also serve as geometric models in computer graphics, collision detection, and engineering. Their half-space descriptions make containment tests straightforward: a point lies inside exactly when it satisfies every defining inequality. Polyhedral meshes are used in numerical methods, including the finite element method.
Their usefulness has several limits:
- Convexity excludes cavities and indentations. More complicated solids require nonconvex representations or decomposition into convex pieces.
- Flat faces only approximate curved boundaries. Greater geometric accuracy generally requires more faces.
- Equivalent descriptions can differ greatly in size. In variable dimension, a short inequality description can correspond to exponentially many vertices, or conversely.
- Numerical degeneracy can complicate computation. Nearly coplanar faces and nearly coincident vertices require careful geometric tests; rounding errors can otherwise produce inconsistent face structures.