Ham sandwich theorem

It was proposed by Hugo Steinhaus and proved by Stefan Banach (explicitly in dimension 3, without stating the theorem in the n-dimensional case), and also years later called the Stone–Tukey theorem after Arthur H. Stone and John Tukey.

According to Beyer & Zardecki (2004), the earliest known paper about the ham sandwich theorem, specifically the n = 3 case 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 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?"

A more modern reference is Stone & 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 Stanislaw Ulam, based on information from a referee; but Beyer & Zardecki (2004) claim that this is incorrect, given the note mentioned above, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem.

; the fraction of pancake #1 covered by the line changes continuously from 0 to 1, so by the intermediate value theorem it must be equal to 1/2 somewhere along the way.

This proof follows the one described by Steinhaus and others (1938), attributed there to Stefan Banach, for the n = 3 case.

In the field of Equivariant topology, this proof would fall under the configuration-space/tests-map paradigm.

Let A1, A2, ..., An denote the n compact (or more genreral: bounded and Lebesgue-measurable) subsets of

, which is the side pointed to by the vector v. By the intermediate value theorem, every family of such hyperplanes contains at least one hyperplane that bisects the bounded set 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 closed interval Iv of possible values of

as follows: This function f is continuous (which can be proven with the dominated convergence theorem).

means that the volume of Ai is the same on the positive and negative side of

is the desired ham sandwich cut that simultaneously bisects the volumes of A1, ..., An.

In measure theory, Stone & 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.

, there is a point p of the n-sphere Sn and a real number s0 such that the surface f(p,x) = s0 divides X into f(p,x) < s0 and f(p,x) > s0 of equal measure and simultaneously bisects the outer measure of X1, X2, ..., Xn.

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.

In two dimensions, the theorem can be stated as follows: There is an exceptional case when points lie on the line.

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

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.

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.

Finally, Lo & Steiger (1990) found an optimal O(n)-time algorithm.

This algorithm was extended to higher dimensions by Lo, Matoušek & Steiger (1994) where the running time is

If d is a part of the input, then no polynomial time algorithm is expected to exist, as if the points are on a moment curve, the problem becomes equivalent to necklace splitting, which is PPA-complete.

A linear-time algorithm that area-bisects two disjoint convex polygons is described by Stojmenovíc (1991).

The original theorem works for at most n collections, where n 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 k, i.e., an (n−1)–dimensional surface defined by a polynomial function of degree k: Given

measures in an n–dimensional space, there exists an algebraic surface of degree k which bisects them all.