ISEGORIA / MATH ENCYCLOPEDIA
Convex geometry: shapes, hulls, and duality
A set is convex if it contains the straight segment between any two of its points. That single rule is enough to build a rich geometry. A convex body is described completely by how far it reaches in every direction, its support function. Two convex bodies can be added shape by shape, and their support functions simply add. Every body that contains the origin has a polar twin that trades vertices for faces and corners for tangent planes. And two convex bodies that do not touch can always be pulled apart by a plane, with the width of the widest gap equal to the shortest distance between them. These facts sit underneath linear programming, the maximum-margin classifier, collision detection in games and the isoperimetric inequality. The three experiments take polar duality apart in three dimensions, add shapes and watch their reach add, and compute the shortest distance between two polyhedra.
Before you begin: Vectors and dot products in the plane and in space, area and volume, the maximum of a function over a set
Predict, manipulate, then test yourself: every experiment ends with practice questions that are generated fresh at three levels. Graphs illustrate the mathematics; they do not replace a proof.
1. Polar duality: every point a tangent plane
For a convex body \(K\) containing the origin, the polar \(K^\circ\) is the set of all \(y\) with \(\langle x,y\rangle\le1\) for every \(x\in K\). Each \(y\) stands for the plane \(\langle x,y\rangle=1\), which misses the interior of \(K\); the nearer \(y\) is to the boundary of \(K^\circ\), the nearer the plane comes to touching \(K\). For the unit ball of a norm the polar is the unit ball of the dual norm, so the \(\ell_p\) ball has the \(\ell_q\) ball as its polar, with \(1/p+1/q=1\). Slide \(s=1/p\) from the cube (\(p=\infty\)) through the ball (\(p=2\)) to the octahedron (\(p=1\)) and watch the two bodies trade places. Because scaling \(K\) by \(c\) scales \(K^\circ\) by \(1/c\), the product \(\mathrm{vol}K\cdot\mathrm{vol}K^\circ\), Mahler’s volume product, depends on shape alone. It is least for the cube and octahedron and greatest for the ball.
Worked example. The cube \([-1,1]^3\) has volume 8 and its polar is the octahedron \(|y_1|+|y_2|+|y_3|\le1\) of volume \(4/3\), so the product is \(32/3=10.67\). The ball and its own polar give \((4\pi/3)^2=17.55\). In between, \(p=3\) and \(q=3/2\) give \(8\Gamma(4/3)^3=5.696\) and \(8\Gamma(5/3)^3/2=2.943\), product 16.76. For \(p=3\) take the point \(y=3^{-2/3}(1,1,1)\) of \(K^\circ\). It stands for the plane \(x_1+x_2+x_3=3^{2/3}=2.080\), at distance \(1/|y|=3^{1/6}=1.201\) from the centre, and that plane touches \(K\) at \(x^*=3^{-1/3}(1,1,1)=(0.693,0.693,0.693)\), where \(\langle x^*,y\rangle=1\).
Watch out. The volume formula and the polar of an \(\ell_p\) ball hold for \(1\le p\le\infty\), which is why \(s\) is limited to \([0,1]\). At the cube and the octahedron the surfaces are drawn from a fine grid, so edges look very slightly rounded. That the product is at least \(32/3\) for every centrally symmetric body is Mahler’s conjecture: it is proved in dimensions two and three (the three-dimensional case by Iriyeh and Shibata in 2020) and open from dimension four. The upper bound is the Blaschke–Santaló inequality, with equality only for ellipsoids.
Why does the polar of the cube turn out to be the octahedron, with six vertices where the cube had six faces?
Each face of the cube \([-1,1]^3\) lies in a plane \(x_i=\pm1\), which is \(\langle x,y\rangle=1\) for \(y=\pm e_i\): one face gives one vertex of the polar, six in all. Each of the eight corners \(\varepsilon=(\pm1,\pm1,\pm1)\) of the cube gives the condition \(\langle\varepsilon,y\rangle\le1\), which is one face of the polar, eight in all. So vertices and faces trade places, edges correspond to edges, and the counts \((V,E,F)=(8,12,6)\) become \((6,12,8)\).
2. Minkowski sums: shapes that add
The Minkowski sum of two sets is \(A+B=\{a+b:a\in A,\,b\in B\}\): put a copy of \(B\) at every point of \(A\), or slide \(B\) around the edge of \(A\) and keep everything it covers. The reach of a body in direction \(u\), its support function \(h_A(u)=\max_{a\in A}\langle a,u\rangle\), determines a convex body completely, and under Minkowski addition it behaves like ordinary addition, \(h_{A+B}=h_A+h_B\). If \(B\) is a disc of radius \(t\) the sum is the parallel body of \(A\), and its area splits into the area of \(A\), a strip along every edge and a circular wedge at every corner: Steiner’s formula. For other \(B\) the area is a quadratic in \(t\) with a mixed area \(V(A,B)\) in the middle, and the Brunn–Minkowski inequality says that square roots of areas always add up at least as fast as the areas of sums allow.
Worked example. Let \(A\) be the square \([-1,1]^2\) (area 4, perimeter 8) and \(B\) the unit disc with \(t=0.5\). In direction \(\theta=0\) the reach is \(1+0.5=1.5\). Steiner gives \(|A+tD|=4+8(0.5)+\pi(0.5)^2=8.785\): the square, four strips of area 1 and four wedges of total area 0.785. Two aligned squares of sides 2 and 1 sum to a square of side 3 and area 9, and \(\sqrt9=3=\sqrt4+\sqrt1\): equality, since they are homothetic. An equilateral triangle \(A\) and its half-turn \(-A\) are not: \(A+(-A)\) is a hexagon of area \(6|A|\), so the ratio is \(\sqrt6/2=1.2247\).
Watch out. The experiment works with polygons: the disc is a 180-sided polygon, so the Steiner area shown is exact only to about one part in 5000, and a segment has zero area, so its Brunn–Minkowski ratio is just \(\sqrt{|A+B|/|A|}\). The formula for \(|A|\) in terms of \(h\) needs \(h\) to be differentiable, and for polygons it holds as an integral of piecewise smooth pieces. The picture shows the region centred on the origin, so every support function is positive.
When is the Brunn–Minkowski inequality an equality?
Exactly when \(A\) and \(B\) are homothetic, meaning \(B\) is a scaled and translated copy of \(A\) (same shape, same way up). Then \(A+B\) is just \(A\) scaled by \(1+c\), its area is \((1+c)^2|A|\) and its square root is \((1+c)\sqrt{|A|}=\sqrt{|A|}+\sqrt{|B|}\). Any other pair, such as two squares at different angles, or a square and a disc, gives a strict inequality.
3. Hulls and separating planes
The convex hull of a finite set of points is the smallest convex body containing them: a polyhedron whose corners are some of the points, with Euler’s count \(V-E+F=2\). Two disjoint convex bodies can always be separated by a plane. To find the best one, look for the closest pair of points \(p\in A\), \(q\in B\): the plane through the midpoint, perpendicular to \(q-p\), leaves a margin of \(d/2\) on each side. Equivalently, over all unit directions \(n\) the gap \(\min_B\langle n,x\rangle-\max_A\langle n,x\rangle\) is largest, equal to the distance \(d\), exactly along \(q-p\). Tilt the direction and the gap shrinks. The shortest distance and the widest separating slab are one number seen from two sides, which is the geometry of the maximum-margin classifier.
Worked example. Let \(A\) be the cube \([-1,1]^3\) and \(B\) the same cube moved by \((3,3,3)\). The closest points are the corners \(p=(1,1,1)\) and \(q=(2,2,2)\), so \(d=\sqrt3=1.732\), \(n^*=(1,1,1)/\sqrt3\), and the separating plane is \(x+y+z=4.5\) through the midpoint \((1.5,1.5,1.5)\), with margin \(\sqrt3/2=0.866\) either side. Along the \(x\) axis alone the gap is only \(3-2=1\). Moved by \((3,3,0)\) instead, two vertical edges face each other and \(d=\sqrt2\). A cube against an octahedron of corner distance 1.4, centred at \((4,0,0)\), has \(d=4-1.4-1=1.6\), from a tip to a face.
Watch out. The distance is computed exactly for polyhedra, by trying every vertex against every face and every edge against every edge, which is fast for the handful of points here but is not how one treats thousands. For smooth bodies the closest pair is found iteratively instead. The hulls of the cloud are computed afresh each time from its twelve points, three of which are swallowed. When the bodies overlap there is no separating plane and the gap is negative in every direction.
Why is the best separating direction the one along the shortest segment between the two bodies?
Any plane that separates \(A\) from \(B\) must cross every segment from a point of \(A\) to a point of \(B\), in particular the closest pair \(p,q\). The gap along a unit direction \(n\) is at most \(\langle n,q-p\rangle\le|q-p|=d\), by the Cauchy–Schwarz inequality, with equality exactly when \(n\) points along \(q-p\). And that direction does achieve \(d\), because the planes through \(p\) and \(q\) perpendicular to \(q-p\) support \(A\) and \(B\), by the minimality of the pair. So \(d\) is both an upper bound and attained.