Convex Geometry

Convex geometry is the study of convex sets: sets in which the straight segment joining any two points of the set stays inside it.

9 frameworks, from 1880 to today · Geometry · Mathematics

still a working view ended · each leads to its entry below

Overview

Convex geometry is the study of convex sets: sets in which the straight segment joining any two points of the set stays inside it123. A disk, a cube, a triangle, and the region above a parabola are convex; a crescent, a star, and a doughnut are not3. The subject asks what follows from this one simple property. It turns out that an enormous amount follows, and that the answers connect to optimization, probability, number theory, physics, and computer science. What is at stake is a kind of rigidity: convexity forbids dents and holes, and that restriction forces quantitative laws relating a body's volume, its surface, its width in different directions, and the number of pieces needed to describe it. The history of convex geometry is the story of discovering those laws, then discovering that they hold far beyond the smooth, familiar shapes where they were first seen.

Ancient roots and the slow start

Convexity was used long before it was named. Archimedes, in the third century BCE, proved that the surface area of a sphere is two-thirds that of the circumscribing cylinder and that a sphere's volume is two-thirds the cylinder's—results that rest on convex reasoning about enclosing and enclosed figures. The method of exhaustion, which approximates a curved region from inside and outside by polygons, is a convexity argument in disguise. Greek geometers also knew that the shortest path between two points is a straight line, the seed of the idea that convex bodies minimize distance.

For nearly two thousand years, though, convexity remained a tool rather than a subject. The decisive shift came in the nineteenth century, when mathematicians began to ask systematic questions about convex sets as objects in their own right.

Support, duality, and the classical theory

The founding move of classical convexity is the supporting hyperplane: a flat plane that touches a convex body along its boundary without cutting into it. In two dimensions this is a supporting line; in three, a supporting plane. The key fact is that every boundary point of a closed convex body has at least one supporting hyperplane through it. This gives a way to describe a convex body from outside, by the family of all half-spaces that contain it.

That description leads to convex duality. A convex body can be encoded by its support function, which records, for each direction, how far the body extends in that direction4. The body is the intersection of the half-spaces cut out by its supporting hyperplanes, so the support function determines the body completely4. Duality turns questions about points inside a body into questions about functions of direction, and vice versa. Hermann Minkowski, in work published around the turn of the twentieth century, made this precise and used it to characterize which functions can be support functions of a convex body.

Minkowski also introduced the operation now called Minkowski addition: given two convex bodies, form the set of all sums of a point from one and a point from the other. Adding a disk to a square rounds its corners; adding a long thin segment stretches it. Minkowski addition is the natural "vector space" structure on convex bodies, and it became the backbone of the field.

The Brunn–Minkowski theory

The central theorem of classical convex geometry is the Brunn–Minkowski inequality5. It says that the volume of the Minkowski sum of two bodies, raised to the power 1/n in n dimensions, is at least the average of the two bodies' volumes raised to that power. In symbols, for bodies K and L in n-dimensional space,

$$\mathrm{vol}(K+L)^{1/n} \ge \mathrm{vol}(K)^{1/n} + \mathrm{vol}(L)^{1/n}.$$

Hermann Brunn proved a version in the 1880s, and Minkowski gave a proof for the general case in the 1890s. The inequality is striking because it is an equality exactly when the two bodies are homothetic—scaled copies of one another—so it measures how far two shapes are from being similar.

From Brunn–Minkowski flows a whole family of results. Slicing a convex body by parallel hyperplanes, the areas of the slices behave in a controlled, concave way (the Brunn–Minkowski theorem for sections). The isoperimetric inequality—among all bodies of a given volume, the ball has the least surface area—is a corollary. So is the fact that among all bodies of given volume, the ball maximizes the mean width. These are the "laws" of convex geometry, and they say that the ball is extremal in many senses at once.

A parallel development concerned mixed volumes: the volume of a Minkowski sum expands as a polynomial in the scaling parameters, and its coefficients are the mixed volumes, which encode how the bodies interact. Minkowski's mixed-volume inequalities and the Alexandrov–Fenchel inequality (proved by Aleksandr Alexandrov and Werner Fenchel in the late 1930s) organize this theory. The Brunn–Minkowski theory, as this whole complex is called, remains the gravitational center of the field.

Polytopes and combinatorial convexity

A polytope is a convex body with finitely many extreme points—a polygon in the plane, a polyhedron in space, and their higher-dimensional analogues. Polytopes are the combinatorial skeleton of convex geometry: every convex body can be approximated by polytopes, and many questions reduce to counting their faces.

Euler's formula for polyhedra, V − $E + F = 2$, relating vertices, edges, and faces, is the oldest result here. Its higher-dimensional generalization, the Euler–Poincaré relation, was established in the nineteenth century. The modern combinatorial theory took off in the twentieth century with the question of which numbers of faces a polytope can have. The Upper Bound Theorem, conjectured in the 1950s and proved by Peter McMullen in 1970, gives the maximum number of faces of each dimension for a polytope with a fixed number of vertices; the extremal examples are the cyclic polytopes. The g-theorem, conjectured by McMullen and proved by Richard Stanley in 1980 using algebraic methods, characterizes exactly which face-number sequences occur. Stanley's proof imported techniques from commutative algebra—the face ring of a polytope—and showed that combinatorial convexity and algebra could feed each other.

A related strand is the study of oriented matroids, abstractions of the combinatorial structure of point configurations, which capture which subsets lie on which sides of which hyperplanes. These grew out of work on arrangements of hyperplanes and on the "allowable sequences" of points moving in the plane, and they let combinatorialists reason about convex position without coordinates.

Helly-type theorems

In 1913, Eduard Helly proved a startling fact: if a finite family of convex sets in n-dimensional space has the property that every n+1 of them share a common point, then all of them share a common point. In the plane, if every three convex sets overlap, all of them do. This is the prototype of a Helly-type theorem, and it is the reason convexity is so useful in feasibility questions: local consistency implies global consistency.

Helly's theorem spawned a family. The Radon theorem (1887) says any n+2 points in n-space can be split into two groups whose convex hulls intersect. Carathéodory's theorem (1907) says any point in the convex hull of a set in n-space lies in the convex hull of at most n+1 of the original points. These three—Helly, Radon, Carathéodory—are the classical pillars of combinatorial convexity, and they are logically intertwined6. Later work extended them to non-convex settings, to families with bounded intersection numbers, and to quantitative versions (how many points must overlap, how large the intersection is), a line of research that remains active.

Linear programming and the geometry of optimization

In the 1940s, George Dantzig developed the simplex method for linear programming: maximizing or minimizing a linear function subject to linear inequalities. Geometrically, the feasible region is a polytope, and the optimum occurs at a vertex. The simplex method walks from vertex to vertex along edges, improving the objective at each step.

This practical success raised a theoretical question: why does the method work, and how fast is it? The geometry of polytopes became central. The duality theorem of linear programming—that the maximum of a linear function over a polytope equals the minimum of a related function over a dual polytope—is a concrete instance of convex duality, and it has an economic reading as a price equilibrium. The study of how many vertices a polytope can have, and how the vertices are connected, became a branch of convex geometry with direct algorithmic consequences. The Hirsch conjecture, posed in 1957, asked whether the graph of a polytope with N facets in dimension d always has diameter at most N − d; it was disproved in 2010 by Francisco Santos, who constructed a counterexample, showing that the combinatorial geometry of polytopes still holds surprises.

Asymptotic geometric analysis

In the second half of the twentieth century, a new perspective emerged: instead of studying one convex body, study the typical behavior of convex bodies in very high dimension. This is asymptotic geometric analysis, sometimes called the local theory of Banach spaces, because a convex body symmetric about the origin defines a norm, and the geometry of that norm is the geometry of a Banach space.

The surprise is that high-dimensional convex bodies behave very differently from low-dimensional intuition. A ball in a thousand dimensions has almost all its volume concentrated in a thin shell near its surface, and a random direction is almost orthogonal to any fixed direction. These concentration phenomena make high-dimensional convexity both strange and tractable. Landmark results include the Dvoretzky theorem (1961), which says that every high-dimensional convex body contains almost-Euclidean sections of dimension growing with the dimension, and the Brunn–Minkowski theory's high-dimensional refinements, such as the Blaschke–Santaló inequality and its stability versions. The field matured through the 1980s and 1990s with contributions from Vitali Milman, Joram Lindenstrauss, and many others, and it remains one of the most active parts of convex geometry.

Convexity in optimal transport and Monge–Ampère theory

A separate tradition connects convexity to partial differential equations. Optimal transport asks how to move one distribution of mass to another at least cost7. In the 1940s, Leonid Kantorovich formulated the problem as a linear program over measures, and the dual problem involves convex functions. When the cost is the squared distance, the optimal map is the gradient of a convex function—a fact that ties transport to the Monge–Ampère equation, a fully nonlinear PDE whose solutions are convex potentials.

This connection, developed through the twentieth century and given a modern geometric form by Robert McCann and others in the 1990s, made convexity a tool in analysis and geometry. The Brunn–Minkowski inequality itself can be proved by transport arguments, and the theory of Ricci curvature lower bounds in metric spaces, developed by Lott, Sturm, and Villani, is built on convexity of entropy along transport paths. Here convexity is not just a property of sets but a structural principle for functions and measures.

Discrete convex analysis

In the 1980s and 1990s, a parallel theory arose for functions on integer lattices. Discrete convex analysis, developed by Kazuo Murota and others, defines notions such as L-convex and M-convex functions—discrete analogues of convex functions—for which greedy algorithms and exchange properties hold. The motivation came from combinatorial optimization: submodular functions, matroids, and valuated matroids have convex-like structure, and discrete convex analysis gives a unified language for them. It is a young branch, still growing, and it shows that the convexity idea can be transplanted from continuous space to discrete settings.

Computational convex geometry

With the rise of computers, convex geometry acquired an algorithmic face. Computational convex geometry studies algorithms for computing convex hulls, for deciding whether a point lies in a convex body, for optimizing linear functions over polytopes, and for approximating convex bodies by simpler ones. The convex hull of a finite point set can be computed in time polynomial in the number of points and the dimension, though the dependence on dimension is severe. Randomized algorithms, such as Seidel's linear-programming algorithm and the ellipsoid method of Khachiyan (1979), which proved that linear programming is solvable in polynomial time, are landmarks. The interplay between convex geometry and algorithms continues: the study of polytope diameters, of the complexity of vertex enumeration, and of convex optimization in high dimension are all active.

The present

Convex geometry today is a federation of approaches. The Brunn–Minkowski theory remains central, with active work on stability versions, on the equality cases of its inequalities, and on extensions to non-convex and discrete settings. Asymptotic geometric analysis continues to probe high-dimensional phenomena, with connections to probability, functional analysis, and machine learning. Combinatorial convexity and polytope theory are driven by questions from optimization and from algebraic combinatorics, and the g-theorem and its generalizations remain a model of cross-fertilization. Optimal transport has become a major bridge between convexity and PDE, and discrete convex analysis is finding applications in economics and combinatorial optimization. Computational convex geometry is increasingly intertwined with convex optimization and with the theory of algorithms.

The open questions are many: the precise structure of high-dimensional convex bodies, the complexity of polytope algorithms, the stability of geometric inequalities, and the extension of convexity to discrete and non-Euclidean settings. What unites them is the original insight—that a single, simple restriction, the absence of dents, generates a rich and rigid mathematical world.

References

  1. Convex geometry, Wikipedia
  2. Convex analysis, Wikipedia
  3. Convex set, Wikipedia
  4. Support function, Wikipedia
  5. Brunn–Minkowski theorem, Wikipedia
  6. Carathéodory's theorem (convex hull), Wikipedia
  7. Transportation theory (mathematics), Wikipedia

The frameworks of Convex Geometry

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1880-Present

    Brunn–Minkowski Theory

    How does volume behave under adding convex bodies?

    Fly to its tower in Nousfarer

  2. 1890-Present

    Classical Convexity Theory

    How can a convex body be described from outside?

    Fly to its tower in Nousfarer

  3. 1900-Present
  4. 1907-Present

    Helly-type Theory

    When does local overlap force global overlap?

    Fly to its tower in Nousfarer

  5. 1940-Present
  6. 1947-Present

    Geometry of Linear Programming

    Where does a linear objective reach its optimum?

    Fly to its tower in Nousfarer

  7. 1961-Present

    Asymptotic geometry

    What happens to convex bodies in high dimension?

    Fly to its tower in Nousfarer

  8. 1970-Present

    Computational Convex Geometry

    How can convex structures be computed efficiently?

    Fly to its tower in Nousfarer

  9. 1980-Present

    Discrete Convex Analysis

    What is the discrete analogue of a convex function?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Brunn–Minkowski TheoryClassical Convexity TheoryPolyhedral combinatoricsHelly-type TheoryConvexity in Optimal Transport and Mo…Geometry of Linear ProgrammingAsymptotic geometryComputational Convex GeometryDiscrete Convex Analysis

Beyond the field

Where Convex Geometry's ideas came from in other fields, and what they led to there: the strongest 12 of 31 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Convex Geometry is a planet in Nousfarer

Its city has a tower for each of these 9 frameworks. Land, walk in, and climb one concept at a time.

Land on Convex Geometry

Related fields

Fields its ideas are linked to

More in Geometry

See where Convex Geometry sits on the Map of Human Knowledge