In mathematical measure theory, for every positive integer the ham sandwich theorem states that given measurable "objects" in -dimensional Euclidean space, it is possible to divide each one of them in half (with respect to their measure, e.g. volume) with a single -dimensional hyperplane. This is even possible if the objects overlap.
It was proposed by Hugo Steinhaus and proved by Stefan Banach (explicitly in dimension 3, without taking the trouble to state the theorem in the -dimensional case), and also years later called the Stone–Tukey theorem after Arthur H. Stone and John Tukey.
The ham sandwich theorem takes its name from the case when and the three objects to be bisected are the ingredients of a ham sandwich. Sources differ on whether these three ingredients are two slices of bread and a piece of ham, bread and cheese and ham, or bread and butter and ham . In two dimensions, the theorem is known as the pancake theorem to refer to the flat nature of the two objects to be bisected by a line .
According to, the earliest known paper about the ham sandwich theorem, specifically the case of bisecting three solids with a plane, is a 1938 note in a Polish mathematics journal . Beyer and Zardecki's paper includes a translation of this note, which attributes the posing of the problem to Hugo Steinhaus, and credits Stefan Banach as the first to solve the problem, by a reduction to the Borsuk–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 is, which is the basis of the name "Stone–Tukey theorem". This paper proves the -dimensional version of the theorem in a more general setting involving measures. The paper attributes the case to Stanislaw Ulam, based on information from a referee; but claim that this is incorrect, given the note mentioned above, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem.
The two-dimensional variant of the theorem (also known as the pancake theorem) can be proved by an argument which appears in the fair cake-cutting literature (see e.g. Robertson–Webb rotating-knife procedure).
For each angle
\alpha\in[0,180\circ]
\alpha
\alpha
-infty
infty
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
\alpha
p(\alpha)
p(0)>1/2
p
When the knife is at angle 180, the knife is upside-down, so
p(180)<1/2
p(\alpha)=1/2
The ham sandwich theorem can be proved as follows using the Borsuk–Ulam theorem. This proof follows the one described by Steinhaus and others (1938), attributed there to Stefan Banach, for the case. In the field of Equivariant topology, this proof would fall under the configuration-space/tests-map paradigm.
Rn
Now we define a function from the -sphere to -dimensional Euclidean space
Rn-1
vol of on the positive side of, vol of on the positive side of, ..., vol of on the positive side of .This function is continuous (which, in a formal proof, would need some justification). By the Borsuk–Ulam theorem, there are antipodal points and on the sphere such that . Antipodal points and correspond to hyperplanes and that are equal except that they have opposite positive sides. Thus, means that the volume of is the same on the positive and negative side of (or), for . Thus, (or) is the desired ham sandwich cut that simultaneously bisects the volumes of .
In measure theory, proved two more general forms of the ham sandwich theorem. Both versions concern the bisection of subsets of a common set, where has a Carathéodory outer measure and each has finite outer measure.
f\colonSn x X\toR
Their second formulation is as follows: for any measurable functions over that are linearly independent over any subset of of positive measure, there is a linear combination such that the surface, dividing into and, simultaneously bisects the outer measure of . This theorem generalizes the standard ham sandwich theorem by letting and letting, for, be the -th coordinate of .
In discrete geometry and computational geometry, the ham sandwich theorem usually refers to the special case in which each of the sets being divided is a finite set of points. Here the relevant measure is the counting measure, which simply counts the number of points on either side of the hyperplane. In two dimensions, the theorem can be stated as follows:
For a finite set of points in the plane, each colored "red" or "blue", there is a line that simultaneously bisects the red points and bisects the blue points, that is, the number of red points on either side of the line is equal and the number of blue points on either side of the line is equal.
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, the ham sandwich problem. In two dimensions, the problem is this: given a finite set of points in the plane, each colored "red" or "blue", find a ham sandwich cut for them. First, 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, gave an algorithm for the general two-dimensional case; the running time of their algorithm is, where the symbol indicates the use of Big O notation. Finally, found an optimal -time algorithm. This algorithm was extended to higher dimensions by where the running time is
o(nd-1)
A linear-time algorithm that area-bisects two disjoint convex polygonsis described by.
The original theorem works for at most collections, where is the number of dimensions. To bisect a larger number of collections without going to higher dimensions, one can use, instead of a hyperplane, an algebraic surface of degree, i.e., an –dimensional surface defined by a polynomial function of degree :
Given
\binom{k+n}{n}-1
This generalization is proved by mapping the –dimensional plane into a
\binom{k+n}{n}-1
.