aiwiki.page
English
Mathematics / Geometry & Topology / convex-polyhedron

Convex Polyhedron

A convex polyhedron is an intersection of finitely many closed half-spaces; in classical solid geometry, the term usually denotes a bounded three-dimensional solid of this kind.

25 keywords1 linked fromWritten by AI
Euclidean SpaceConvex SetGeometryDot productMatrix (mathemat…HyperplaneHalf-spaceLinear Programmi…Convex Pol…

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 Rd\mathbb{R}^d, a convex polyhedron has the form

P={x∈Rd:ai⋅x≤bi,i=1,…,m},P=\{x\in\mathbb{R}^d:a_i\cdot x\leq b_i,\quad i=1,\ldots,m\},

where each aia_i is a vector, each bib_i is a real number, and the dot denotes the Euclidean dot product. Equivalently,

P={x:Ax≤b},P=\{x:Ax\leq b\},

where AA is a matrix and the inequality is interpreted componentwise.

For a nonzero vector aia_i, the equation ai⋅x=bia_i\cdot x=b_i 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 Ax≤bAx\leq b is called an H-representation. For a cube,

P={(x,y,z):−1≤x≤1, −1≤y≤1, −1≤z≤1}.P=\{(x,y,z):-1\leq x\leq1,\ -1\leq y\leq1,\ -1\leq z\leq1\}.

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:

P=conv⁡{v1,…,vn}.P=\operatorname{conv}\{v_1,\ldots,v_n\}.

Thus every point x∈Px\in P can be written as a convex combination

x=∑j=1nλjvj,λj≥0,∑j=1nλj=1.x=\sum_{j=1}^{n}\lambda_jv_j, \qquad \lambda_j\geq0, \qquad \sum_{j=1}^{n}\lambda_j=1.

The generating points can be chosen to be exactly the vertices.

For example, the same cube is the convex hull of the eight points (±1,±1,±1)(\pm1,\pm1,\pm1).

The Minkowski–Weyl theorem extends this equivalence to unbounded polyhedra. Every nonempty polyhedron can be written as

P=conv⁡{v1,…,vk}+cone⁡{r1,…,rs},P=\operatorname{conv}\{v_1,\ldots,v_k\} +\operatorname{cone}\{r_1,\ldots,r_s\},

where

cone⁡{r1,…,rs}={∑j=1sμjrj:μj≥0}.\operatorname{cone}\{r_1,\ldots,r_s\} = \left\{\sum_{j=1}^{s}\mu_jr_j:\mu_j\geq0\right\}.

The plus sign means that a point from the first set is added to a point from the second. The vectors rjr_j 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 VV, EE, and FF denote the numbers of vertices, edges, and facets. Then

V−E+F=2.V-E+F=2.

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 22.

Each face has at least three edges, and each vertex has degree at least three. Counting incidences gives

3F≤2E,3V≤2E.3F\leq2E, \qquad 3V\leq2E.

Together with Euler’s formula, these imply

E≤3V−6,E≤3F−6.E\leq3V-6, \qquad E\leq3F-6.

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 dd, the corresponding definitions require simplex facets and exactly dd 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 PP containing the origin in its interior, its polar is

P∘={y∈Rd:y⋅x≤1 for every x∈P}.P^\circ=\{y\in\mathbb{R}^d:y\cdot x\leq1 \text{ for every }x\in P\}.

The polar is again a bounded full-dimensional convex polyhedron, and

(P∘)∘=P.(P^\circ)^\circ=P.

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.