The Ham-Sandwich Theorem

Picture a sandwich flying through the air: a slice of ham and a slab of bread, tumbling, no longer neatly stacked. Can a single straight stroke of the knife cut both of them exactly in half at the same moment?

It sounds like it should depend on luck — surely you'd have to line them up first. The astonishing answer is no: a fair cut always exists, no matter how the two pieces are scattered or shaped. This is the ham-sandwich theorem, and it is not a heuristic or an approximation. It is a proven mathematical fact.

In the flat version we care about here, "ham" and "bread" become two clouds of points, and the knife becomes a straight line. The promise stands: one line, two perfect halves.

Here are two point clouds — the ham (red) and the bread (blue). The ham-sandwich theorem promises one straight line that puts half the red points on each side and half the blue points on each side, all at once. Click to add your own points, then press the button.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="420" height="300"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="shuffle" type="button">{{btn_new}}</button>
  <button id="mode" type="button" class="ghost">{{btn_mode_ham}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.red { color: #e63946; }
.blue { color: #1d6fb8; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f7fafc; cursor: crosshair; touch-action: none; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The computer sweeps the line's direction through every angle. For each angle it places the line so it bisects the ham, then checks how the bread splits. The theorem guarantees that somewhere along that sweep, the bread balances too — and the line snaps into place. Try moving the points anywhere you like: a fair cut is always waiting to be found.

So why does the cut always exist, and how hard is it to actually find?

• The status: proven. The ham-sandwich theorem was conjectured by Steinhaus and proved by Arthur Stone and John Tukey in 1942. In d dimensions, d measurable "ingredients" can always be simultaneously bisected by a single hyperplane.
• Why it must exist. The proof rides on the Borsuk-Ulam theorem from topology: any continuous map from a sphere to a lower-dimensional space must send some pair of antipodal points to the same value. Turn "how the bread splits" into such a continuous function of the cutting direction, and Borsuk-Ulam forces a direction where the split is perfectly even. Existence is guaranteed — no luck required.
• Finding it is fast. Locating the line is not an intractable search. In the plane, Lo, Matoušek and Steiger (1994) gave an algorithm that finds a ham-sandwich cut for n points in $O(n)$ — linear — time. The brute-force angle sweep in the demo is the slow, intuitive cousin of that result.

This is the opposite of an open problem like P vs NP: the answer is known, the cut always exists, and we can compute it efficiently. The theorem's charm is not difficulty but certainty — a guarantee that geometry hands you for free.

"Split several things fairly with one decision" turns up far beyond lunch:

• Fair division. The theorem is the geometric backbone of dividing resources so multiple parties each get an even share along a single boundary.
• Balanced partitioning. In computational geometry, ham-sandwich cuts split point sets into balanced halves — useful for building divide-and-conquer data structures and search trees.
• Redistricting and fairness arguments. It appears in formal discussions of carving a region into pieces that balance two populations at once.
• Higher dimensions. With more ingredients, one hyperplane can balance several distributions simultaneously, a tool in statistics and discrete geometry.

The same flavor of "balance everything at once" shows up whenever we want structure to be even rather than lopsided — a cousin of the balance sought in graph coloring and partitioning problems.

The ham-sandwich theorem wears a comic name over a profound idea: no matter how two shapes are strewn across the plane, a single straight cut splits both into equal halves — and the proof, through Borsuk-Ulam, leaves no room for exceptions.

Even better, the cut isn't hidden behind intractability. We can compute it in linear time. So while many problems on this site are about what we cannot do, the ham-sandwich theorem is a reminder of the other side: sometimes mathematics quietly promises that the thing you want always exists — and hands you a fast way to find it. Curious about a problem where no such guarantee exists? See P vs NP.