Ham sandwich theorem

From Wikipedia, the free encyclopedia

In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone–Tukey theorem after Marshall Stone and John Tukey, states that given n "objects" in n-dimensional space, it is possible to divide each one in half (according to volume) with a single (n − 1)-dimensional hyperplane. Here the "objects" should be sets of finite measure (or, in fact, just of finite outer measure) for the notion of "dividing the volume in half" to make sense.

1 Naming
2 History
3 Reduction to the Borsuk–Ulam theorem
4 Measure theoretic statement
5 Discrete and computational geometry versions
- 5.1 Proof
6 "Leftovers"
7 References
8 External links

[edit] Naming

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

a chunk of ham,
a slice of cheese, and
two slices of bread (treated as a single disconnected object).

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

[edit] History

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.

[edit] Reduction to 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 A₁, A₂, ..., A_n denote the n objects that we wish to simultaneously bisect. Let S be the unit (n − 1)-sphere in $\mathbb{R}^n$ , 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 A_n: at one extreme translation, no volume of A_n is on the positive side, and at the other extreme translation, all of A_n's volume is on the positive side, so in between there must be a translation that has half of A_n'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 A_n 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 A_n.

Now we define a function f from the (n − 1)-sphere S to (n − 1)-dimensional Euclidean space $\mathbb{R}^{n-1}$ as follows:

f(p) = (

volume of A₁ on the positive side of π(p),

volume of A₂ on the positive side of π(p),

...,

volume of A_n−1 on the positive side of π(p)

This function f is continuous. By the Borsuk–Ulam theorem, there are antipodal points p and q on the sphere S such that f(p) = f(q). Antipodal points p and q correspond to hyperplanes π(p) and π(q) that are equal except that they have opposite positive sides. Thus, f(p) = f(q) means that the volume of A_i is the same on the positive and negative side of π(p) (or π(q)), for i = 1, 2, ..., n − 1. Thus, π(p) (or π(q)) is the desired ham sandwich cut that simultaneously bisects the volumes of A₁, A₂, ..., A_n.

[edit] Measure theoretic statement

In measure theory, a more general form of the ham sandwich theorem is due to Stone and Tukey (1942): for any n subsets X₁, X₂, ..., X_n of any set X with a Carathéodory outer measure, there is a suitably restricted real function $f : S^n \times X \to \mathbb{R}$ , where $S n$ is the n-sphere, that simultaneously divides each of the n subsets in half with respect to the measure.

[edit] Discrete and computational geometry versions

A ham-sandwich cut of eight red points and seven blue points in the plane.

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 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 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 their ham sandwich cut. After a series of papers with various solutions to this problem, Lo and Steiger (1990) found an optimal O(n)-time algorithm. This algorithm is randomized, but Lo, Matousek, and Steiger (1994) showed how it could be derandomized into a deterministic algorithm with O(n) running time in the worst case.

[edit] Proof

The discrete two-dimensional form of the ham-sandwich theorem can be proved directly using continuity as follows.

First we show that, for every angle θ, there is an oriented line of angle θ that bisects the red set of points. To see this, just slide an oriented line of angle θ perpendicularly; at one extreme, all the red points are on the left side of the line, and at the other extreme, all the red points are on the right side of the line, so by continuity there is a position in between where they are equal. More precisely, we can consider the continuous function f mapping the perpendicular offset of the line to the difference between the number of red points on the left and the number of red points on the right; at one extreme, f is r (the number of red points), and at the other extreme f is −r, so by the intermediate value theorem, somewhere in between, f must be zero, corresponding to a red bisector.

Second we argue the existence of a red bisector that is also a blue bisector. Look at the red bisector of angle 0 obtained from the previous step. This line has some number b₁ of blue points on its left, and some number b₂ of blue points on its right. Now consider a red bisector of angle 180°, namely, the reverse of the previous line. This line has b₂ blue points on its left and b₁ points on its right. If we define g(θ) to be the difference between the number of blue points on the left and right of the red bisector of angle θ, then g(0) = b₁ − b₂ and g(180°) = b₂ − b₁. By the intermediate value theorem, there must be an angle θ for which g(θ) = 0, corresponding to a simultaneous red and blue bisector. (Here we omit the proof that g is in fact continuous.)

[edit] "Leftovers"

Byrnes, Cairns, and Jessup (2001) showed that it is not always possible to position the hyperplane correctly just by cutting through the objects' center of gravity.

[edit] References

Beyer, W. A. & Zardecki, Andrew (Jan. 2004). "The early history of the ham sandwich theorem". American Mathematical Monthly 111 (1), 58–61.

Lo, Chi-Yuan & Steiger, W. L. (1990). "An optimal time algorithm for ham-sandwich cuts in the plane". In Proceedings of the Second Canadian Conference on Computational Geometry, pp. 5–9.