The Ham Sandwich Theorem: One Hyperplane Bisects n Finite-Measure Sets in ℝⁿ

What the ham sandwich theorem says

Let A₁, …, A_n be Lebesgue-measurable subsets of ℝⁿ, each of finite measure. The ham sandwich theorem asserts that there exists an affine hyperplane H = {x : ⟨u, x⟩ = c} with unit normal u such that, for every i,

λ(A_i ∩ {⟨u, x⟩ ≤ c}) = λ(A_i ∩ {⟨u, x⟩ ≥ c}) = ¹⁄₂ λ(A_i),

where λ is Lebesgue measure. One hyperplane, n sets, all of them halved at the same time.

• n = 1: a bounded measurable set on the line has a median point that splits its length in half. This is just the intermediate value theorem applied to c ↦ λ(A ∩ (−∞, c]).
• n = 2: any two shapes in the plane — a pancake and a puddle, a country and its coastline — are halved by a single straight line. This is the case the animation proves.
• n = 3: any three solids in space are halved by a single flat plane. Two slices of bread and a slice of ham: the sandwich.

The hypotheses that matter are measurability and finite measure. Nothing else is required: the sets may be disconnected, non-convex, fractal in outline, nested, or overlapping. What the theorem does not give you is uniqueness, a construction, or any control over where the cut lands.

The plane case, proved by turning one line

Fix a direction and write u(θ) = (cos θ, sin θ) for the normal. Slide a line with that normal across the picture: the ham on the u-negative side grows continuously from nothing, when the line is below everything, to all of it, when the line is above everything. Somewhere in between it is exactly half. That is the intermediate value theorem, and it fixes an offset c*(θ).

Now define the bread imbalance

g(θ) = λ(B ∩ blue side) − λ(B ∩ purple side).

Turning the direction by half a turn gives back the same line — because u(θ + π) = −u(θ) and c*(θ + π) = −c*(θ) — but with the two sides swapped. Therefore

g(θ + π) = −g(θ).

If g is continuous, it runs from some value to its exact negative, so by the intermediate value theorem it is zero at some θ*. The line at that angle halves the ham by construction and halves the bread because g(θ*) = 0. One line, both shapes halved.

When is this a proof rather than a picture? It is a complete proof whenever c*(θ) is well defined and continuous. That holds for any bounded open connected set: the projection of a connected set onto a line is an interval, and an open set meets every open slab inside that interval in a nonempty open set, hence in positive area — so the area-to-the-left function is strictly increasing, the half-area offset is unique, and it varies continuously with θ because the area is jointly continuous in (θ, c). Convex bodies with positive area are a special case. For a general measurable set the half-area offsets can form a whole interval (imagine a dumbbell whose bar has zero thickness), the natural selection can jump, and the argument has to be routed through Borsuk–Ulam instead. The animation uses two open connected blobs, so what it shows is the real thing, computed by exact polygon clipping rather than asserted.

Borsuk–Ulam: the engine underneath

The general theorem rests on the Borsuk–Ulam theorem, conjectured by Stanisław Ulam and proved by Karol Borsuk in Fundamenta Mathematicae in 1933: for every continuous map f : Sⁿ → ℝⁿ there is a point x with f(x) = f(−x). You cannot flatten a sphere into one lower dimension without gluing some antipodal pair together. The usual gloss: at any instant there are two antipodal points on Earth with the same temperature and the same pressure.

The reduction goes like this. Identify ℝⁿ with the affine copy {x_n+1 = 1} inside ℝⁿ⁺¹. Each unit vector v ∈ Sⁿ determines a closed half-space H_v = {y : ⟨v, y⟩ ≥ 0}, which meets that copy of ℝⁿ in a half-space, in all of it, or in nothing. Define

f(v) = ( λ(A₁ ∩ H_v), …, λ(A_n ∩ H_v) ) ∈ ℝⁿ.

• Why f is continuous: a hyperplane has Lebesgue measure zero, so nudging v changes each coordinate by the measure of a thin slab, which tends to 0. This is exactly where “Lebesgue-measurable with finite measure” earns its keep; a measure with an atom sitting on a hyperplane would make f jump.
• Apply Borsuk–Ulam: some v has f(v) = f(−v). Since H_v and H_−v are complementary up to a null set, each A_i is split into two equal halves.
• The degenerate directions: if v = ±(0, …, 0, 1) the half-space swallows all of ℝⁿ or none of it, so f(v) and f(−v) differ in every coordinate unless every set is null. Those poles cannot be the solution, so the v we get really does define a genuine hyperplane.

The planar rotating-line proof is this same argument with S² replaced by a circle of directions, and Borsuk–Ulam in dimension 1 replaced by the intermediate value theorem — which is precisely the n = 1 case of Borsuk–Ulam.

Steinhaus, Banach, Stone and Tukey: where the sandwich came from

The problem is Polish, and it comes out of the Lwów school that met in the Scottish Café. Hugo Steinhaus published the three-dimensional question in Mathesis Polska in 1938 and reported that Stefan Banach had solved it by deriving it from the Borsuk–Ulam theorem — a theorem then only five years old. Steinhaus also credited a two-dimensional forerunner to Herbert Auerbach. The historical record was assembled by W. A. Beyer and Andrew Zardecki in “The early history of the ham sandwich theorem,” American Mathematical Monthly 111 (2004), 58–61, who also translated the 1938 note.

The version mathematicians actually cite is Arthur H. Stone and John W. Tukey, “Generalized ‘sandwich’ theorems,” Duke Mathematical Journal 9 (1942), 356–359. Stone and Tukey did three things: they stated the result for arbitrary finite measures in ℝⁿ, they removed the smoothness assumptions earlier arguments leaned on, and they replaced hyperplanes by far more general bisecting surfaces — the generalisation that would resurface seventy years later as polynomial partitioning.

The name is a joke that stuck. For n = 3 the three sets are two slices of bread and the ham between them; the claim is that a single straight swipe of the knife can halve all three however carelessly the sandwich was assembled. The colloquial name appears in print by the 1940s and is now standard in both topology and computational geometry.

Sharpness: what the theorem does not say

Every clause of the statement is doing work, and the failures are concrete.

• n + 1 sets in ℝⁿ is false. Put three unit disks at the vertices of a non-degenerate triangle in the plane. A line halves a disk if and only if it passes through the centre, so a common bisector would have to contain three non-collinear points. None exists. The count n sets for n dimensions is exactly right, not merely sufficient.
• The cut is not unique. Two concentric disks are halved by every line through the common centre — a one-parameter family of solutions. Conversely two unit disks centred at (0, 0) and (3, 0) have exactly one common bisector, the line y = 0 through both centres. Uniqueness depends on the configuration; the theorem never promises it.
• Finite measure is required. “Half” has no meaning for a set of infinite measure: two crossing half-planes cannot be split into equal infinite halves in any well-defined sense.
• Measurability is required. If A is non-measurable, “the area on each side” is not a number, and the continuous function the proof needs does not exist.
• Atoms weaken the conclusion. For general finite Borel measures that charge hyperplanes — point masses, for instance — the map f above can jump, and the correct statement becomes: there is a hyperplane such that each open half-space carries at most half of each measure. For Lebesgue-measurable sets, hyperplanes are null and “exactly half” is recovered.
• It is pure existence. The Borsuk–Ulam proof is non-constructive; it tells you a cut is there and nothing about where to look. That gap is not an artefact of the proof — see the complexity results below.

The discrete version, and how to compute a ham sandwich cut

Computational geometry uses the finite version. Let P₁, …, P_d be finite point sets in ℝ^d. There is a hyperplane H such that each open half-space bounded by H contains at most ⌊|P_i|⁄​2⌋ points of P_i, for every i. The open-half-space wording is not pedantry: with 5 red points, no line can put 2.5 on each side, so the cut must run through one of them. Replacing each point by a tiny disk and applying the continuous theorem, then shrinking the disks, is the standard derivation.

A worked instance: 6 red points and 4 blue points in general position in the plane. The guarantee is at most 3 red and at most 2 blue strictly on either side — a genuine constraint, since a random line typically splits one of the two sets badly.

• The plane: Chi-Yuan Lo, Jiří Matoušek and William Steiger, “Algorithms for ham-sandwich cuts,” Discrete & Computational Geometry 11 (1994), 433–452, find a ham-sandwich cut for two planar point sets of total size n in O(n) time, which is optimal. The method is prune-and-search in the dual, where bisecting lines become points on the median level of a line arrangement. Nimrod Megiddo had earlier solved the linearly separable case in linear time (1985).
• Higher fixed dimension: the same paper gives algorithms in ℝ^d whose running time grows roughly like n^d−1 — polynomial for each fixed d, but useless once d is large.
• Dimension as input: Aris Filos-Ratsikas and Paul Goldberg proved at STOC 2019 that Ham Sandwich, together with Necklace Splitting and Consensus Halving, is PPA-complete. PPA is the complexity class built on the parity argument that underlies Borsuk–Ulam, so the hardness is the exact computational shadow of the proof technique: existence is guaranteed by a parity argument, and no polynomial-time search is expected.

For two polygons the rotating-line proof is the algorithm — this is what the animation runs, frame by frame:

import numpy as np

def area_left(poly, u, c):            # area of poly on the side {u.x <= c}
    return polygon_area(clip_halfplane(poly, u, c))

def bisecting_offset(poly, u, iters=40):
    lo, hi = (poly @ u).min(), (poly @ u).max()
    half = polygon_area(poly) / 2
    for _ in range(iters):            # area_left is increasing in c
        mid = (lo + hi) / 2
        lo, hi = (mid, hi) if area_left(poly, u, mid) < half else (lo, mid)
    return (lo + hi) / 2

def ham_sandwich_cut(ham, bread, iters=60):
    def imbalance(t):                 # bread on the left minus bread on the right
        u = np.array([np.cos(t), np.sin(t)])
        c = bisecting_offset(ham, u)
        return 2 * area_left(bread, u, c) - polygon_area(bread), u, c
    a, b = 0.0, np.pi                 # imbalance(b) == -imbalance(a): a root lies between
    fa = imbalance(a)[0]
    for _ in range(iters):            # bisection on the angle, not on the offset
        m = (a + b) / 2
        fm = imbalance(m)[0]
        if (fm > 0) == (fa > 0): a, fa = m, fm
        else: b = m
    _, u, c = imbalance((a + b) / 2)
    return u, c                       # the cut {x : u.x == c} halves both

Two nested bisections — one on the offset, one on the angle — converge to the cut used in the video, which halves both blobs to a relative error below 10⁻⁹.

Descendants: polynomial cuts, distinct distances, and stolen necklaces

The ham sandwich theorem is not a curiosity; it is a load-bearing tool, and the generalisation Stone and Tukey added in 1942 is the reason.

• Polynomial ham sandwich. Lift ℝ^d by the Veronese map, sending x to the vector of all monomials of degree at most D. A hyperplane upstairs pulls back to the zero set of a degree-D polynomial downstairs. So if N ≤ C(D + d, d) − 1, then N measures in ℝ^d can be simultaneously bisected by a real algebraic hypersurface of degree at most D. With D = 1 this is the original theorem.
• Polynomial partitioning. Iterating that bisection on a point set produces a polynomial of degree D whose complement has O(D^d) cells, each holding at most about n⁄D^d of the n points. Larry Guth and Nets Hawk Katz used exactly this in “On the Erdős distinct distances problem in the plane,” Annals of Mathematics 181 (2015), 155–190, proving that n points in the plane determine at least c·n⁄log n distinct distances — a problem Paul Erdős posed in 1946 and which had stood for 64 years. Polynomial partitioning is now standard in incidence geometry and harmonic analysis.
• Necklace splitting. Two thieves steal an open necklace with t types of beads, an even number of each: t cuts always suffice to divide it fairly, and t is optimal. Charles Goldberg and Douglas West proved that two-thief case in 1985; Noga Alon gave the general k-thief version, (k − 1)t cuts, in “Splitting necklaces,” Advances in Mathematics 63 (1987), 247–253. The two-thief proof maps the necklace onto the moment curve in ℝ^t and applies the ham sandwich theorem to the t bead measures; the bisecting hyperplane meets the curve in at most t points, and those are the cuts.
• Fair division and elections. Consensus halving — splitting a resource so that every one of n agents values the two parts equally — is the continuous cousin, and it is the PPA-complete problem from which the hardness of ham sandwich cuts was derived. The same circle of ideas underwrites results on balanced partitions and on bisecting a district map by a single straight boundary.

The pattern is always the same: an antipodal symmetry on a sphere, a continuous map into one dimension less, and a conclusion that something must be exactly balanced — without the faintest hint of where.

One cut, how many sets? The ham sandwich theorem dimension by dimension

Setting	Sets bisected	The cut	Status and cost
ℝ¹ — the line	1 set of finite measure	A single point (a median)	Immediate from the intermediate value theorem
ℝ² — the plane	2 measurable sets	One straight line	The rotating-line argument; linear time for point sets (Lo–Matoušek–Steiger, 1994)
ℝ³ — space	3 solids: bread, ham, bread	One flat plane	The namesake case; Banach's Borsuk–Ulam proof, 1938
ℝⁿ	n measurable sets of finite measure	One affine hyperplane	Stone–Tukey, 1942; PPA-complete when the dimension is part of the input (2019)
ℝⁿ	n + 1 sets	One hyperplane	False in general — three unit disks at the corners of a triangle have no common bisector