Introduction

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.

Cut the Sandwich

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">Two point clouds — <b class="red">ham</b> and <b class="blue">bread</b>.
    The ham-sandwich theorem promises a single straight line that cuts <b>both</b> exactly
    in half at once. Drop points, then let the computer find that one line.</p>
<canvas id="cv" width="420" height="300"></canvas>
<div class="status" id="status">Add points or press "Find the cut".</div>
<div class="btns">
  <button id="find" type="button">Find the cut</button>
  <button id="shuffle" type="button">New clouds</button>
  <button id="mode" type="button" class="ghost">Adding: 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Ham-sandwich theorem (Stone & Tukey, 1942): for any two finite point sets in the plane there is ONE straight line that simultaneously bisects both — equal points on each side. Existence is guaranteed; here we FIND the line by sweeping the angle.
// For each direction theta we take the line (perpendicular to theta) that bisects set A, then measure how balanced B is across it. The theorem says some theta balances both; we pick the angle minimising B's imbalance.
const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;
let A = [], B = [], adding = 'A', line = null;

function rand(n, cx, cy, s){ const p=[]; for(let i=0;i<n;i++)
  p.push({x: cx + (Math.random()-0.5)*s, y: cy + (Math.random()-0.5)*s}); return p; }
function seed(){ A = rand(7, 130, 110, 150); B = rand(7, 290, 190, 150); line = null; }

// Median offset along direction (cos t, sin t): the value c such that half the points have x*cos+y*sin <= c. With an odd count the median splits evenly.
function medianProj(pts, t){ const co=Math.cos(t), si=Math.sin(t);
  const v = pts.map(p => p.x*co + p.y*si).sort((a,b)=>a-b);
  const m = v.length; return v[Math.floor((m-1)/2)]; // lower median
}
// Count strictly above / below the line {dir t, offset c}.
function split(pts, t, c){ const co=Math.cos(t), si=Math.sin(t); let lo=0, hi=0;
  for(const p of pts){ const d = p.x*co + p.y*si - c; if(d < -1e-9) lo++; else if(d > 1e-9) hi++; }
  return {lo, hi};
}
function imbalance(pts, t, c){ const s = split(pts, t, c); return Math.abs(s.lo - s.hi); }

function findCut(){
  if(A.length===0 || B.length===0){ setStatus('Add at least one point to each cloud.',''); return; }
  let best=null, bestScore=Infinity;
  const STEPS = 720;
  for(let i=0;i<STEPS;i++){
    const t = Math.PI * i / STEPS;          // direction of the normal, 0..pi
    const c = medianProj(A, t);             // line that bisects A in this direction
    const score = imbalance(A,t,c) + imbalance(B,t,c);
    if(score < bestScore){ bestScore = score; best = {t, c, score}; }
  }
  line = best;
  const sa = split(A, best.t, best.c), sb = split(B, best.t, best.c);
  render();
  setStatus(fmt('One line — ham %lo%|%hi%, bread %lo2%|%hi2%. Both bisected!', { lo: sa.lo, hi: sa.hi, lo2: sb.lo, hi2: sb.hi }),
            best.score===0 ? 'ok' : '');
  console.log('cut', {theta:best.t, offset:best.c, A:sa, B:sb, imbalance:best.score});
}

function lineEndpoints(t, c){ // normal=(cos t,sin t), points satisfy x*co+y*si=c
  const co=Math.cos(t), si=Math.sin(t);
  // pick the larger component to avoid division blow-up
  if(Math.abs(si) > Math.abs(co)){
    return [{x:-1000, y:(c+1000*co)/si}, {x:W+1000, y:(c-(W+1000)*co)/si}];
  } else {
    return [{x:(c+1000*si)/co, y:-1000}, {x:(c-(H+1000)*si)/co, y:H+1000}];
  }
}
function dot(p, col){ ctx.beginPath(); ctx.arc(p.x,p.y,6,0,7); ctx.fillStyle=col; ctx.fill();
  ctx.lineWidth=1.5; ctx.strokeStyle='#fff'; ctx.stroke(); }
function render(){
  ctx.clearRect(0,0,W,H);
  if(line){ const e=lineEndpoints(line.t,line.c); ctx.beginPath();
    ctx.moveTo(e[0].x,e[0].y); ctx.lineTo(e[1].x,e[1].y);
    ctx.lineWidth=3; ctx.strokeStyle='#0a7d33'; ctx.setLineDash([8,5]); ctx.stroke(); ctx.setLineDash([]); }
  A.forEach(p=>dot(p,'#e63946'));
  B.forEach(p=>dot(p,'#1d6fb8'));
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

cv.addEventListener('click', e=>{ const r=cv.getBoundingClientRect();
  const x=(e.clientX-r.left)*W/r.width, y=(e.clientY-r.top)*H/r.height;
  (adding==='A'?A:B).push({x,y}); line=null; render(); setStatus('Point added. Press "Find the cut".',''); });
document.getElementById('find').addEventListener('click', findCut);
document.getElementById('shuffle').addEventListener('click', ()=>{ seed(); render(); setStatus('New clouds. Press "Find the cut".',''); });
document.getElementById('mode').addEventListener('click', e=>{ adding = adding==='A'?'B':'A';
  e.target.textContent = fmt('Adding: %v%', { v: adding==='A'?'ham':'bread' }); });

seed(); render();
Result
Console

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.

The Real Complexity

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)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ham-sandwich/Content licensed under CC BY-NC 4.0.