Ham sandwich theorem

Inmathematicalmeasure theory, for every positive integerntheham sandwich theoremstates that givennmeasurable"objects" inn-dimensionalEuclidean space, it is possible to divide each one of them in half (with respect to theirmeasure, e.g. volume) with a single(n− 1)-dimensionalhyperplane. This is possible even if the objects overlap.
It was proposed byHugo Steinhausand proved byStefan Banach(explicitly in dimension 3, without stating the theorem in then-dimensional case), and also years later called theStone–Tukey theoremafterArthur H. StoneandJohn Tukey.
The ham sandwich theorem takes its name from the case whenn= 3and the three objects to be bisected are the ingredients of aham sandwich. Sources differ on whether these three ingredients are two slices of bread and a piece of ham (Peters 1981), bread and cheese and ham (Cairns 1963), or bread and butter and ham (Dubins & Spanier 1961). In two dimensions, the theorem is known as thepancake theoremto refer to the flat nature of the two objects to be bisected by a line (Cairns 1963).
According toBeyer & Zardecki (2004), the earliest known paper about the ham sandwich theorem, specifically then= 3case of bisecting three solids with a plane, is a 1938 note in a Polish mathematics journal (Editors 1938).  Beyer and Zardecki's paper includes a translation of this note, which attributes the posing of the problem toHugo Steinhaus, and creditsStefan Banachas the first to solve the problem, by a reduction to theBorsuk–Ulam theorem.  The note poses the problem in two ways: first, formally, as "Is it always possible to bisect three solids, arbitrarily located, with the aid of an appropriate plane?" and second, informally, as "Can we place a piece of ham under a meat cutter so that meat, bone, and fat are cut in halves?"  The note then offers a proof of the theorem.
A more modern reference isStone & Tukey (1942), which is the basis of the name "Stone–Tukey theorem".  This paper proves then-dimensional version of the theorem in a more general setting involving measures.  The paper attributes then= 3case toStanislaw Ulam, based on information from a referee; butBeyer & Zardecki (2004)claim that this is incorrect, given the note mentioned above, although "Ulam did make a fundamental contribution in proposing" theBorsuk–Ulam theorem.
The two-dimensional variant of the theorem (also known as thepancake theorem) can be proved by an argument which appears in thefair cake-cuttingliterature (see e.g.Robertson–Webb rotating-knife procedure).
For each angleα∈[0,180∘]{\displaystyle \alpha \in [0,180^{\circ }]}, a straight line ("knife") of angleα{\displaystyle \alpha }can bisect pancake #1.  To see this, translate along itsnormala straight line of angleα{\displaystyle \alpha }from−∞{\displaystyle -\infty }to∞{\displaystyle \infty }; the fraction of pancake #1 covered by the line changes continuously from 0 to 1, so by theintermediate value theoremit must be equal to 1/2 somewhere along the way. It is possible that an entire range of translations of our line yield a fraction of 1/2; in this case, it is a canonical choice to pick the middle one of all such translations.
When the knife is at angle 0, it also cuts pancake #2, but the pieces are probably unequal (if we are lucky and the pieces are equal, we are done). Define the 'positive' side of the knife as the side in which the fraction of pancake #2 is larger. We now turn the knife, and translate it as described above. When the angle isα{\displaystyle \alpha }, definep(α){\displaystyle p(\alpha )}as the fraction of pancake #2 at the positive side of the knife. Initiallyp(0)>1/2{\displaystyle p(0)>1/2}. The functionp{\displaystyle p}is continuous, since small changes in the angle lead to small changes in the position of the knife.
When the knife is at angle 180, the knife is upside-down, sop(180)<1/2{\displaystyle p(180)<1/2}. By theintermediate value theorem, there must be an angle in whichp(α)=1/2{\displaystyle p(\alpha )=1/2}. Cutting at that angle bisects both pancakes simultaneously.
The ham sandwich theorem can be proved as follows using theBorsuk–Ulam theorem.  This proof follows the one described by Steinhaus and others (1938), attributed there toStefan Banach, for then= 3case. In the field ofEquivariant topology, this proof would fall under the configuration-space/tests-map paradigm.
LetA1,A2, ...,Andenote thencompact(or more genreral:boundedandLebesgue-measurable) subsets ofRn{\displaystyle \mathbb {R} ^{n}}that we wish to simultaneously bisect.  LetS={v=(v1,…,vn)∈Rn:v12+…+vn2=1}{\displaystyle S=\{v=(v_{1},\ldots ,v_{n})\in \mathbb {R} ^{n}\colon v_{1}^{2}+\ldots +v_{n}^{2}=1\}}be theunit(n− 1)-sphereinRn{\displaystyle \mathbb {R} ^{n}}.  For each pointvonS, we can define acontinuum(Ev,c)c∈R{\displaystyle (E_{v,c})_{c\in \mathbb {R} }}of affinehyperplaneswithnormal vectorv:Ev,c={x∈Rn:x1v1+…+xnvn=c}{\displaystyle E_{v,c}=\{x\in \mathbb {R} ^{n}\colon x_{1}v_{1}+\ldots +x_{n}v_{n}=c\}}forc∈R{\displaystyle c\in \mathbb {R} }. For eachc∈R{\displaystyle c\in \mathbb {R} }, we call the spaceEv,c+={x∈Rn:x1v1+…+xnvn>c}{\displaystyle E_{v,c}^{+}=\{x\in \mathbb {R} ^{n}\colon x_{1}v_{1}+\ldots +x_{n}v_{n}>c\}}the "positive side" ofEv,c{\displaystyle E_{v,c}}, which is the side pointed to by the vectorv. By theintermediate value theorem, every family of such hyperplanes contains at least one hyperplane that bisects the bounded setAn: at one extreme translation, no volume ofAnis on the positive side, and at the other extreme translation, all ofAn's volume is on the positive side, so in between there must be a closed intervalIvof possible values ofc∈R{\displaystyle c\in \mathbb {R} }, for whichEv,c{\displaystyle E_{v,c}}bisects the volume ofAn. IfAnhas volume zero, we pickc=0{\displaystyle c=0}for allv∈S{\displaystyle v\in S}. Otherwise, the intervalIvis compact and we can canonically pickc=12(infIv+supIv){\displaystyle c={\frac {1}{2}}(\inf I_{v}+\sup I_{v})}as its midpoint for eachv∈S{\displaystyle v\in S}. Thus we obtain a continuous functionα:S→R{\displaystyle \alpha \colon S\to \mathbb {R} }such that for each pointvon the sphereSthe hyperplaneEv,α(v){\displaystyle E_{v,\alpha (v)}}bisectsAn. Note further that we haveI−v=−Iv{\displaystyle I_{-v}=-I_{v}}and thusα(−v)=−α(v){\displaystyle \alpha (-v)=-\alpha (v)}for allv∈S{\displaystyle v\in S}.
Now we define a functionf:S→Rn−1{\displaystyle f\colon S\to \mathbb {R} ^{n-1}}as follows:
This functionfiscontinuous(which can be proven with thedominated convergence theorem).  By theBorsuk–Ulam theorem, there areantipodal pointsv{\displaystyle v}and−v{\displaystyle -v}on the sphereSsuch thatf(v)=f(−v){\displaystyle f(v)=f(-v)}.  Antipodal points correspond to hyperplanesEv,α(v){\displaystyle E_{v,\alpha (v)}}andE−v,α(−v)=E−v,−α(v){\displaystyle E_{-v,\alpha (-v)}=E_{-v,-\alpha (v)}}that are equal except that they have opposite positive sides.  Thus,f(v)=f(−v){\displaystyle f(v)=f(-v)}means that the volume ofAiis the same on the positive and negative side ofEv,α(v){\displaystyle E_{v,\alpha (v)}}, fori=1,…,n{\displaystyle i=1,\ldots ,n}.  Thus,Ev,α(v){\displaystyle E_{v,\alpha (v)}}is the desired ham sandwich cut that simultaneously bisects the volumes ofA1, ...,An.
Inmeasure theory,Stone & Tukey (1942)proved two more general forms of the ham sandwich theorem.  Both versions concern the bisection ofnsubsetsX1,X2, ...,Xnof a common setX, whereXhas aCarathéodoryouter measureand eachXihas finite outer measure.
Their first general formulation is as follows: for any continuous realfunctionf:Sn×X→R{\displaystyle f\colon S^{n}\times X\to \mathbb {R} }, there is a pointpof then-sphereSand a real numbers0such that the surfacef(p,x) =s0dividesXintof(p,x) <s0andf(p,x) >s0of equal measure and simultaneously bisects the outer measure ofX1,X2, ...,Xn.  The proof is again a reduction to the Borsuk-Ulam theorem.  This theorem generalizes the standard ham sandwich theorem by lettingf(s,x) =s1x1+ ... +snxn.
Their second formulation is as follows: for anyn+ 1measurable functionsf0,f1, ...,fnoverXthat arelinearly independentover any subset ofXof positive measure, there is alinear combinationf=a0f0+a1f1+ ... +anfnsuch that the surfacef(x) = 0, dividingXintof(x) < 0andf(x) > 0, simultaneously bisects the outer measure ofX1,X2, ...,Xn.  This theorem generalizes the standard ham sandwich theorem by lettingf0(x) = 1and lettingfi(x), fori> 0, be thei-th coordinate ofx.
Indiscrete geometryandcomputational geometry, the ham sandwich theorem usually refers to the special case in which each of the sets being divided is afinite setofpoints.  Here the relevant measure is thecounting measure, which simply counts the number of points on either side of the hyperplane.  In two dimensions, the theorem can be stated as follows:
There is an exceptional case when points lie on the line.  In this situation, we count each of these points as either being on one side, on the other, or on neither side of the line (possibly depending on the point), i.e. "bisecting" in fact means that each side contains less than half of the total number of points.  This exceptional case is actually required for the theorem to hold, of course when the number of red points or the number of blue is odd, but also in specific configurations with even numbers of points, for instance when all the points lie on the same line and the two colors are separated from each other (i.e. colors don't alternate along the line). A situation where the numbers of points on each side cannot match each other is provided by adding an extra point out of the line in the previous configuration.
In computational geometry, this ham sandwich theorem leads to a computational problem, theham sandwich problem.  In two dimensions, the problem is this: given a finite set ofnpoints in the plane, each colored "red" or "blue", find a ham sandwich cut for them.  First,Megiddo (1985)described an algorithm for the special, separated case. Here all red points are on one side of some line and all blue points are on the other side, a situation where there is a unique ham sandwich cut, which Megiddo could find in linear time. Later,Edelsbrunner & Waupotitsch (1986)gave an algorithm for the general two-dimensional case; the running time of their algorithm isO(nlogn), where the symbolOindicates the use ofBig O notation. Finally,Lo & Steiger (1990)found an optimalO(n)-timealgorithm. This algorithm was extended to higher dimensions byLo, Matoušek & Steiger (1994)where the running time iso(nd−1){\displaystyle o(n^{d-1})}. Givendsets of points in general position ind-dimensional space, the algorithm computes a(d−1)-dimensional hyperplane that has an equal number of points of each of the sets in both of its half-spaces, i.e., a ham-sandwich cut for the given points. Ifdis a part of the input, then no polynomial time algorithm is expected to exist, as if the points are on amoment curve, the problem becomes equivalent tonecklace splitting, which isPPA-complete.
A linear-time algorithm that area-bisects two disjoint convex polygons
is described byStojmenovíc (1991).
The original theorem works for at mostncollections, wherenis the number of dimensions. To bisect a larger number of collections without going to higher dimensions, one can use, instead of a hyperplane, analgebraic surfaceofdegreek, i.e., an (n−1)–dimensional surface defined by a polynomial function of degreek:
Given(k+nn)−1{\displaystyle {\binom {k+n}{n}}-1}measures in ann–dimensional space, there exists an algebraic surface of degreekwhich bisects them all. (Smith & Wormald (1998)).
This generalization is proved by mapping then–dimensional plane into a(k+nn)−1{\displaystyle {\binom {k+n}{n}}-1}dimensional plane, and then applying the original theorem. For example, forn= 2andk= 2, the 2–dimensional plane is mapped to a 5–dimensional plane via: