The ham sandwich theorem takes its name from the case when n = 3 and the three objects of any shape are a chunk of ham and two chunks of bread — notionally, a sandwich — which can then each be bisected with a single cut (i.e., a plane). In two dimensions, the theorem is known as the pancake theorem of having to cut two infinitesimally thin pancakes on a plate each in half with a single cut (i.e., a straight line).
The ham sandwich theorem is also sometimes referred to as the "ham and cheese sandwich theorem", again referring to the special case when n = 3 and the three objects are
The theorem then states that it is possible to slice the ham and cheese sandwich in half such that each half contains the same amount of bread, cheese, and ham. It is possible to treat the two slices of bread as a single object, because the theorem only requires that the portion on each side of the plane vary continuously as the plane moves through 3-space.
The ham sandwich theorem has no relationship to the "squeeze theorem" (sometimes called the "sandwich theorem").
According to Beyer and Zardecki (2004), the earliest known paper about the ham sandwich theorem, specifically the d = 3 case of bisecting three solids with a plane, is by Steinhaus and others (1938). Beyer and Zardecki's paper includes a translation of the 1938 paper. It 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 paper 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?" Later, the paper offers a proof of the theorem.
A more modern reference is Stone and Tukey (1942), which is the basis of the name "Stone–Tukey theorem". This paper proves the n-dimensional version of the theorem in a more general setting involving measures. The paper attributes the n = 3 case to Stanisław Marcin Ulam, based on information from a referee; but Beyer & Zardecki (2004) claim that this is incorrect, given Steinhaus's paper, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem.
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 n = 3 case.
Let A1, A2, …, An denote the n objects that we wish to simultaneously bisect. Let S be the unit (n − 1)-sphere embedded in n-dimensional Euclidean space , centered at the origin. For each point p on the surface of the sphere S, we can define a continuum of oriented hyperplanes perpendicular to the (normal) vector from the origin to p, with the "positive side" of each hyperplane defined as the side pointed to by that vector. By the intermediate value theorem, every family of such hyperplanes contains at least one hyperplane that bisects the bounded object An: at one extreme translation, no volume of An is on the positive side, and at the other extreme translation, all of An's volume is on the positive side, so in between there must be a translation that has half of An's volume on the positive side. If there is more than one such hyperplane in the family, we can pick one canonically by choosing the midpoint of the interval of translations for which An is bisected. Thus we obtain, for each point p on the sphere S, a hyperplane π(p) that is perpendicular to the vector from the origin to p and that bisects An.
Now we define a function ƒ from the (n − 1)-sphere S to (n − 1)-dimensional Euclidean space as follows:
In measure theory, Stone and Tukey (1942) proved two more general forms of the ham sandwich theorem. Both versions concern the bisection of n subsets X1, X2, …, Xn of a common set X, where X has a Carathéodory outer measure and each Xi has finite outer measure.
Their first general formulation is as follows: for any suitably restricted real function , there is a point p of the n-sphere such that the surface , dividing X into and , simultaneously bisects the outer measure of X1, X2, …, Xn. The proof is again a reduction to the Borsuk-Ulam theorem. This theorem generalizes the standard ham sandwich theorem by letting .
Their second formulation is as follows: for any n+1 measurable functions f0, f1, …, fn over X that are linearly independent over any subset of X of positive measure, there is a linear combination such that the surface , dividing X into and , simultaneously bisects the outer measure of X1, X2, …, Xn. This theorem generalizes the standard ham sandwich theorem by letting and letting , for , be the ith coordinate of x.
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:
There is an exceptional case when a point lies on the line. In this situation, we count the point as being on either both sides of the line or on neither side of the line. This exceptional case is actually required for the theorem to hold, in case the number of red points or the number of blue is odd, and still each set must be bisected.
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 n points 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 and Waupotitsch (1986) gave an algorithm for the general two-dimensional case; the running time of their algorithm is O(n log n). Finally, Lo and Steiger (1990) found an optimal O(n)-time algorithm. This algorithm was extended to higher dimensions by Lo, Matousek, and Steiger (1994). Given d sets of points in general position in d-dimensional space, the algorithm computes a (d−1)-dimensional hyperplane that has equal numbers of points of each of the sets in each of its half-spaces, i.e., a ham-sandwich cut for the given points.