Geometry

Convex and discrete geometry

Studies convex shapes, lattices and arrangements of finitely many geometric objects.

IntuitionLine segments that never leave the shape, and how tightly objects pack

Stretch a rubber band around a handful of pins on a board: the region it encloses has no dents — every straight segment between two points inside stays completely inside. That single property is convexity, and its minimal wrapper around a set $S$ is the convex hull $\operatorname{conv}(S)$ . Discrete geometry pairs convexity with counting and lattices: how many points of $S$ do you actually need to build each point of $\operatorname{conv}(S)$ , when must a convex shape hit a grid point of $\mathbb{Z}^d$ , and how densely can identical spheres be packed in $\mathbb{R}^d$ ?

Explore a 3D convex polyhedron: it is the convex hull of its vertices, and every face is a flat polygon cut out by a supporting hyperplane.

SchoolConvex sets, convex hulls and lattice polygons

A subset $C \subseteq \mathbb{R}^d$ is convex if for every pair of points $x, y \in C$ , the entire line segment joining them lies in $C$ . In the plane $\mathbb{R}^2$ , when the vertices of a simple polygon all sit at integer lattice points of $\mathbb{Z}^2$ , Georg Pick discovered in 1899 that its area can be found purely by counting lattice points — no lengths or angles required.

\forall x, y \in C,\; \forall t \in [0, 1] : (1 - t)x + ty \in C

Here $(1-t)x + ty$ sweeps out the straight segment from $x$ (at $t=0$ ) to $y$ (at $t=1$ ). More generally, the convex hull of any set $S \subseteq \mathbb{R}^d$ is the set of all finite convex combinations of points of $S$ : $\operatorname{conv}(S) = \left\{\, \sum_{i=1}^{k} \lambda_i x_i : x_i \in S,\; \lambda_i \ge 0,\; \sum_{i=1}^{k} \lambda_i = 1 \,\right\}$ .

A = I + \frac{B}{2} - 1

In Pick's formula $A = I + \frac{B}{2} - 1$ , $A$ is the area of a simple lattice polygon in $\mathbb{Z}^2$ , $I$ is the number of lattice points strictly in its interior, and $B$ is the number of lattice points along its boundary edges (including vertices). Every interior point contributes $1$ full unit of area, every boundary point contributes half a unit, and the exterior angle sum subtracts $1$ .

Cornerstone theorems of convex and discrete geometry
Theorem	Dimension	Key threshold / formula
Carathéodory	$\mathbb{R}^d$	$d + 1$ points suffice for $\operatorname{conv}(S)$
Helly	$\mathbb{R}^d$	Every $d + 1$ intersect $\Rightarrow$ all intersect
Minkowski	$\mathbb{R}^d$	$\operatorname{vol}(K) > 2^d \det(\Lambda) \;\Longrightarrow\; K \cap (\Lambda \setminus \{0\}) \neq \emptyset$
Pick	$\mathbb{R}^2$	$A = I + \frac{B}{2} - 1$

UndergraduateCombinatorial convexity and the geometry of numbers

Theorem: Carathéodory's Theorem

If a point $x \in \mathbb{R}^d$ lies in the convex hull $\operatorname{conv}(S)$ of a subset $S \subseteq \mathbb{R}^d$ , then $x$ lies in the convex hull of at most $d + 1$ points of $S$ .

Why is it true?

A convex combination in $\operatorname{conv}(S)$ can a priori involve arbitrarily many points of $S$ , but in $\mathbb{R}^d$ any $d + 2$ or more points are affinely dependent. That linear relation lets you eliminate one point at a time while keeping all weights nonnegative until at most $d + 1$ points remain (a simplex). Helly's theorem — that a finite family of convex sets in $\mathbb{R}^d$ has a common point whenever every $d + 1$ of them do — is a direct sibling of this dimension bound.

Proof

Write $x = \sum_{i=1}^{k} \lambda_i x_i$ with $x_i \in S$ , $\lambda_i > 0$ , and $\sum_{i=1}^{k} \lambda_i = 1$ , chosen so that the number of terms $k$ is minimal. We claim $k \le d + 1$ .

Suppose toward a contradiction that $k \ge d + 2$ . Then the $k - 1 \ge d + 1$ difference vectors $x_2 - x_1, x_3 - x_1, \ldots, x_k - x_1$ in $\mathbb{R}^d$ are linearly dependent, so there exist scalars $\mu_2, \ldots, \mu_k$ , not all zero, such that $\sum_{i=2}^{k} \mu_i (x_i - x_1) = 0$ . Setting $\mu_1 = -\sum_{i=2}^{k} \mu_i$ gives $\sum_{i=1}^{k} \mu_i x_i = 0$ and $\sum_{i=1}^{k} \mu_i = 0$ with at least one $\mu_i > 0$ .

For any real $t$ we have $x = \sum_{i=1}^{k} (\lambda_i - t \mu_i) x_i$ with coefficients summing to $1$ . Choose $t = \min_{\mu_i > 0} (\lambda_i / \mu_i) > 0$ ; then every new coefficient $\lambda_i - t \mu_i$ is nonnegative and at least one becomes $0$ , expressing $x$ as a convex combination of at most $k - 1$ points of $S$ and contradicting the minimality of $k$ .

Theorem: Minkowski's Convex Body Theorem

Let $\Lambda \subset \mathbb{R}^d$ be a full-rank lattice with fundamental domain volume $\det(\Lambda)$ , and let $K \subset \mathbb{R}^d$ be a centrally symmetric convex set ( $x \in K \Rightarrow -x \in K$ ). Then $\operatorname{vol}(K) > 2^d \det(\Lambda) \;\Longrightarrow\; K \cap (\Lambda \setminus \{0\}) \neq \emptyset$ (and if $K$ is also compact, the strict inequality $>$ can be weakened to $\ge$ ).

Why is it true?

It is the continuous pigeonhole principle of number theory: once a symmetric convex body is larger than $2^d$ fundamental cells of the lattice, shrinking it by a factor of $2$ still leaves volume larger than one cell, forcing two points of the shrunk body to differ by a nonzero lattice vector — and symmetry plus convexity pull that lattice vector back inside $K$ .

Proof

Consider the half-sized body $\frac{1}{2} K = \{\, x / 2 : x \in K \,\}$ . Scaling in $d$ dimensions multiplies volume by $2^{-d}$ , so the hypothesis $\operatorname{vol}(K) > 2^d \det(\Lambda)$ becomes $\operatorname{vol}(\frac{1}{2} K) > \det(\Lambda)$ .

Let $F$ be a fundamental parallelepiped of $\Lambda$ , so $\mathbb{R}^d = \bigsqcup_{v \in \Lambda} (F + v)$ and $\operatorname{vol}(F) = \det(\Lambda)$ . Cut $\frac{1}{2} K$ into pieces $A_v = (\frac{1}{2} K) \cap (F + v)$ and translate each piece back into $F$ via $B_v = A_v - v \subseteq F$ . Since the sum of the volumes of the $B_v$ equals $\operatorname{vol}(\frac{1}{2} K) > \operatorname{vol}(F)$ , the sets $B_v$ cannot be pairwise disjoint (Blichfeldt's principle).

Pick distinct lattice vectors $u \neq v$ in $\Lambda$ with $B_u \cap B_v \neq \emptyset$ . Then there exist two distinct points $p, q \in \frac{1}{2} K$ such that $p - u = q - v$ , so $p - q = u - v \in \Lambda \setminus \{0\}$ . Because $p, q \in \frac{1}{2} K$ , we have $2p, 2q \in K$ ; central symmetry of $K$ gives $-2q \in K$ , and convexity of $K$ places the midpoint $\frac{1}{2}(2p) + \frac{1}{2}(-2q) = p - q$ inside $K$ . Thus $p - q$ is a nonzero lattice point in $K \cap (\Lambda \setminus \{0\})$ .

UndergraduateReal-World Applications and Worked Examples

Post-quantum cryptography (such as ML-KEM / Kyber and ML-DSA / Dilithium) rests on the computational hardness of finding the shortest nonzero vector in a high-dimensional lattice $\Lambda \subset \mathbb{R}^d$ , whose existence is guaranteed by Minkowski's theorem. In digital communications, sphere packings in $\mathbb{R}^d$ are error-correcting codes for noisy radio and optical channels: the $24$ -dimensional Leech lattice and the $8$ -dimensional $E_8$ lattice (with optimal packing density $\Delta_{8} = \frac{\pi^4}{384} \approx 0.25367$ ) were used in space-probe telemetry and high-speed modems. In computer graphics, robotics, and GIS, collision detection between 3D meshes reduces to testing whether the origin lies in the Minkowski difference of their convex hulls, while Pick's theorem provides fast grid-based area estimation in digital image processing.

Example: Land parcel area from a GPS lattice grid via Pick's theorem

A triangular land parcel has vertices at the integer grid points $(0, 0)$ , $(4, 0)$ , and $(0, 6)$ in $\mathbb{Z}^2$ . Count the boundary lattice points $B$ and interior lattice points $I$ , and verify that Pick's formula $A = I + \frac{B}{2} - 1$ gives the exact area.

Solution

Along a segment from $(x_1, y_1)$ to $(x_2, y_2)$ , the number of lattice edges is $\gcd(|x_2 - x_1|, |y_2 - y_1|)$ . Summing over the three sides of the triangle gives $B = \gcd(4, 0) + \gcd(0, 6) + \gcd(4, 6) = 4 + 6 + 2 = 12$ boundary lattice points.

For the interior points $(x, y)$ with $x > 0$ , $y > 0$ , and $3x + 2y < 12$ : when $x = 1$ we have $2y < 9$ ( $y \in \{1,2,3,4\}$ , giving $4$ points); when $x = 2$ we have $2y < 6$ ( $y \in \{1,2\}$ , giving $2$ points); when $x = 3$ we have $2y < 3$ ( $y = 1$ , giving $1$ point). Thus $I = 4 + 2 + 1 = 7$ .

Substituting $I = 7$ and $B = 12$ into Pick's formula $A = I + \frac{B}{2} - 1$ gives $A = 7 + 12/2 - 1 = 12$ , which matches the base-times-height calculation $\frac{1}{2} \cdot 4 \cdot 6 = 12$ .

Example: Guaranteeing a nonzero integer solution via Minkowski's theorem

Use Minkowski's convex body theorem to prove that the inequality $x^2 + 9y^2 < 16$ has at least one nonzero integer solution $(x, y) \in \mathbb{Z}^2 \setminus \{(0,0)\}$ , and exhibit one.

Solution

The set $K = \{\, (x, y) \in \mathbb{R}^2 : (x/4)^2 + (3y/4)^2 < 1 \,\}$ is an open ellipse centered at the origin with semi-axes $a = 4$ and $b = 4/3$ , so it is convex and centrally symmetric.

Its area is $\operatorname{vol}(K) = \pi a b = \pi \cdot 4 \cdot (4/3) = 16\pi / 3 \approx 16.755$ . For the standard integer lattice $\Lambda = \mathbb{Z}^2$ in dimension $d = 2$ , we have $\det(\Lambda) = 1$ and Minkowski's threshold is $2^d \det(\Lambda) = 4$ .

Since $16\pi / 3 > 4$ , Minkowski's theorem $\operatorname{vol}(K) > 2^d \det(\Lambda) \;\Longrightarrow\; K \cap (\Lambda \setminus \{0\}) \neq \emptyset$ guarantees a nonzero integer point inside $K$ ; indeed $(1, 1)$ satisfies $1^2 + 9(1)^2 = 10 < 16$ (and $(1, 0)$ , $(2, 0)$ , $(3, 0)$ also lie in $K$ ).

Research frontier as of 2026

In 2016 Maryna Viazovska solved the sphere-packing problem in dimension $8$ by constructing an explicit radial Fourier eigenfunction from modular forms, proving that the $E_8$ root lattice achieves the unique maximum density $\Delta_{8} = \frac{\pi^4}{384} \approx 0.25367$ ; within a week Cohn, Kumar, Miller, Radchenko, and Viazovska extended the method to prove that the Leech lattice is optimal in dimension $24$ , and in 2019 they proved both lattices are universally optimal (minimizing energy for every completely monotonic potential of squared distance). As of 2026, the exact densest sphere packing remains unknown in every dimension $d \ge 4$ except $d = 8$ and $d = 24$ , and in asymptotic convex geometry Bourgain's slicing (hyperplane) conjecture and Mahler's conjecture on the volume product of symmetric convex bodies remain central research fronts.

By Carathéodory's theorem, any point in the convex hull $\operatorname{conv}(S)$ of a set $S \subseteq \mathbb{R}^3$ can be written as a convex combination of at most how many points of $S$ ?

A simple lattice polygon in $\mathbb{Z}^2$ has $I = 10$ interior lattice points and $B = 8$ boundary lattice points. What is its area $A$ ?

For the standard integer lattice $\Lambda = \mathbb{Z}^3$ in $\mathbb{R}^3$ , what volume must a centrally symmetric convex body $K$ exceed for Minkowski's theorem to guarantee a nonzero integer point in $K$ ?

In which pair of dimensions greater than $3$ did Maryna Viazovska and her collaborators prove the exact optimal sphere-packing density in 2016?

References

Peter M. Gruber (2007). Convex and Discrete Geometry (Grundlehren der mathematischen Wissenschaften, Vol. 336) · DOI:10.1007/978-3-540-71133-9
Maryna S. Viazovska (2017). The sphere packing problem in dimension 8 · arXiv:1603.04246
Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, Maryna Viazovska (2019). Universal optimality of the E8 and Leech lattices and interpolation formulas · arXiv:1902.05438