Hammer a handful of nails into a board, stretch a rubber band around them all, and let go. The ring of nails the band catches on is the convex hull of that point set.
What deserves a pause is what it discards: the band never touches the interior nails, and deleting them changes nothing. Most points are redundant; the shape is carried by a few extreme ones.
The convex hull of a point set $S$ is the smallest convex set containing $S$. The constructive version is more computable:
The $x_i$ are points and the $\lambda_i$ are weights; "non-negative and summing to one" is exactly the definition of a weighted average. So the formula reads: the hull is every position a weighted average of these points can land on. Carathéodory's theorem is the quantitative version of the redundancy — in $d$ dimensions, any point of the hull needs a weighted average of at most $d+1$ original points.
Three unrelated definitions — an intersection of sets, a weighted average, a rubber band — land on the same object. Lovelier still is the complexity: the hull of $n$ points in the plane takes $O(n\log n)$, and that is optimal, because sorting reduces to convex hull. Map each number $x$ to the parabola point $(x,x^2)$; the parabola is convex, and the order along the lower half of the hull is precisely the sorted order. Geometry and sorting are the same problem at the level of lower bounds.
A linear program's feasible region is the hull of its constraint vertices, and the simplex method walks from vertex to vertex. Physics engines detect collisions with GJK, which asks whether the Minkowski difference of two hulls contains the origin. The maximum-margin hyperplane of an SVM is the perpendicular bisector of the shortest segment between the two classes' hulls — the "support vectors" are exactly the extreme points that fix the hull's shape, and deleting the rest leaves the model unchanged.
Scatter a few post offices on a map and color every location by which one is nearest. The resulting partition is the Voronoi diagram. The border between two offices is necessarily the perpendicular bisector of the segment joining them.
The Delaunay triangulation is its shadow: connect every pair of sites that share a border and you get a triangular mesh. The two carry identical information — one speaks of territory, the other of adjacency. It is the cleanest duality in geometry.
Given a site set $P$, the cell of a site $p$ is
The condition says "no farther from $p$ than from any other site $q$." Each "$\le$" is a half-space and the cell is their intersection, so every cell is necessarily convex — convexity is not an assumption, it comes for free. The dual side is just as terse: three sites form a Delaunay triangle exactly when no other site lies inside their circumcircle.
First, the lifting trick. Raise each planar point $(x,y)$ onto the paraboloid as $(x,y,x^2+y^2)$, take the lower half of the three-dimensional convex hull, and project it back down: you get exactly the Delaunay triangulation. A nearest-neighbor problem has been translated into a convex hull problem.
Second, Delaunay maximizes the minimum angle among all triangulations, so it is the least prone to slivers — and slivers are precisely what makes numerical solvers diverge. A purely combinatorial definition (the empty circle) turns out to optimize a numerical property. Third, any process where several centers grow outward until they collide must produce a Voronoi diagram — metal grains, cracked mud, cell boundaries.
The geometric body of k-means is Lloyd's algorithm: each round assigns points by the current Voronoi diagram, then moves each center to its cell's centroid — which is why a k-means decision boundary is always a piecewise-linear convex polytope. A robot travelling along Voronoi edges is travelling as far as possible from every obstacle. Mesh generation for CFD and finite elements is Delaunay by default.
How do you stack oranges most efficiently? Lay a hexagonal layer, then drop the next layer into the dimples. Kepler claimed in 1611 that this is the densest possible, at $\pi/\sqrt{18}\approx 74.05\%$.
The hard part is not guessing the answer, it is ruling out every alternative: there are infinitely many candidate arrangements and they need not be periodic, so what must be excluded includes every irregular jumble. Worse, local information lies — a sphere can be surrounded by twelve others and still leave slack, which makes a thirteenth look plausible (Newton said no, Gregory said yes; Newton was right). Local slack does not mean the global packing can be denser.
Packing density is defined as
The $S_i$ are non-overlapping spheres of equal radius and $B_R$ is a ball of radius $R$; letting $R\to\infty$ washes out boundary effects, leaving only the average occupancy far from anywhere. Kepler's conjecture asserts $\delta\le\pi/\sqrt{18}$ in three dimensions. Hales proved it in 1998 by compressing infinitely many configurations into a few thousand finite cases and running numerical optimization on each. The referees spent four years and would only say they were "99% certain"; Hales responded by launching Flyspeck, which delivered a machine-checkable formal proof in 2014.
The terrain across dimensions is wildly non-monotone. $d=2$ was settled by Thue, $d=3$ took four centuries, and $d=4$ through $d=7$ remain entirely open. Then in 2016 Viazovska took $d=8$ and $d=24$ in one stroke — the $E_8$ and Leech lattices are so excessively perfect in those dimensions that her auxiliary function makes the linear-programming upper bound land exactly on the known lower bound, with zero gap. She received the 2022 Fields Medal for it. Low dimensions hard, particular high dimensions exactly solved is a rare piece of counterintuitive terrain.
Sphere packing is the geometric body of error-correcting codes: codewords are sphere centers, the correctable error radius is the sphere radius, so the denser the packing, the more codewords fit at a given correction capacity, and the higher the rate. The Leech lattice gives the best code in 24 dimensions outright and is the ancestor of deep-space modulation constellations. On the materials side, FCC and HCP are the real structures of metal crystals, while spheres simply poured into a container reach about 64% — random close packing, the number that governs powder metallurgy and concrete mix design.
Tile the plane with a single regular polygon and there are exactly three answers: triangle, square, hexagon. The reason fits in your head — the angles around a vertex must sum to $360°$, and the interior angle $\frac{(n-2)180°}{n}$ of a regular $n$-gon divides $360°$ only for $n=3,4,6$. A regular pentagon has interior angle $108°$; three of them make $324°$, leaving $36°$ short.
Generalized, this is the crystallographic restriction theorem: a periodic lattice can only have 2-, 3-, 4- or 6-fold rotational symmetry, and 5-fold is strictly forbidden. That sat in the textbooks for seventy years. Then in 1982 Shechtman saw sharp ten-fold symmetric spots in the diffraction pattern of an aluminium-manganese alloy. He was asked to leave his research group, and Pauling said "there is no such thing as quasicrystals, only quasi-scientists." He took the 2011 Nobel Prize in Chemistry.
An aperiodic set of tiles is a set that tiles the plane while no tiling by it has any translational symmetry. Note the strength of the claim — not "an aperiodic tiling exists" (squares manage that), but "no periodic tiling exists at all." Penrose gave a two-tile example in 1974. A quasicrystal is the material version: a solid whose diffraction pattern has sharp spots yet has no translational period. Mathematically it comes from cut-and-project — five-fold symmetry is perfectly periodic in a five-dimensional lattice, and projecting to the plane loses the period while keeping the order.
"Ordered" and "periodic" were split into two concepts — before this they were treated as synonyms. Penrose tilings have an almost eerie property: any finite patch recurs infinitely often across the whole plane, so no finite window ever tells you where you are, while the whole never repeats itself. And the ratio of kites to darts is exactly the golden ratio $\varphi$ — an irrational number growing out of purely combinatorial matching rules.
In 2023 David Smith and collaborators found "the hat": a single aperiodic tile, closing the sixty-year-old einstein problem (ein Stein, one stone). The first author is an amateur.
Quasicrystalline materials are hard, low-friction, poor heat conductors and corrosion-resistant, used in non-stick and thermal-barrier coatings (the AlCuFe family); aperiodically arranged antenna and ultrasound arrays suppress the grating lobes a periodic layout inevitably produces. The deepest link is on the computer-science side: tiling with Wang tiles is equivalent to the halting problem, so "can this tile set cover the plane?" is undecidable — and the existence of aperiodic sets is a direct consequence of that undecidability. Geometry borders computability right here.