Ham sandwich theorem

Template:Short description Template:Distinguish

In mathematical measure theory, for every positive integer Template:Mvar the ham sandwich theorem states that given Template:Mvar measurable "objects" in Template:Mvar-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 Template:Math-dimensional hyperplane. This is possible even if the objects overlap.

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

NamingEdit

File:Ham sandwich.jpg

A ham sandwich

The ham sandwich theorem takes its name from the case when Template:Math 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 Template:Harv, bread and cheese and ham Template:Harv, or bread and butter and ham Template:Harv. 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 Template:Harv.

HistoryEdit

According to Template:Harvtxt, the earliest known paper about the ham sandwich theorem, specifically the Template:Math case of bisecting three solids with a plane, is a 1938 note in a Polish mathematics journal Template:Harv. 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 Template:Harvtxt, which is the basis of the name "Stone–Tukey theorem". This paper proves the Template:Mvar-dimensional version of the theorem in a more general setting involving measures. The paper attributes the Template:Math case to Stanislaw Ulam, based on information from a referee; but Template:Harvtxt claim that this is incorrect, given the note mentioned above, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem.

Two-dimensional variant: proof using a rotating-knifeEdit

File:Ham sandwich theorem 2d.png

A two-dimensional ham sandwich theorem example with noncontiguous regions: lines at 5° increments bisect the similarly coloured region (pink ham and green vegetable) into two equal areas, the black line denoting the common bisector of both regions

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 <math>\alpha\in[0,180^\circ]</math>, a straight line ("knife") of angle <math>\alpha</math> can bisect pancake #1. To see this, translate along its normal a straight line of angle <math>\alpha</math> from <math>-\infty</math> to <math>\infty</math>; 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. 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 <math>\alpha</math>, define <math>p(\alpha)</math> as the fraction of pancake #2 at the positive side of the knife. Initially <math>p(0) > 1/2</math>. The function <math>p</math> 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, so <math>p(180) < 1/2</math>. By the intermediate value theorem, there must be an angle in which <math>p(\alpha)=1/2</math>. Cutting at that angle bisects both pancakes simultaneously.

n-dimensional variant: proof using the Borsuk–Ulam theoremEdit

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 Template:Math case. In the field of Equivariant topology, this proof would fall under the configuration-space/tests-map paradigm.

Let Template:Math denote the Template:Mvar compact (or more generally bounded and Lebesgue-measurable) subsets of <math>\mathbb{R}^n</math> that we wish to simultaneously bisect. Let <math>S=\{v=(v_1,\ldots,v_n)\in\mathbb{R}^n\colon v_1^2+\ldots+v_n^2=1\}</math> be the unit [[n-sphere|Template:Math-sphere]] in <math>\mathbb{R}^n</math>. For each point Template:Mvar on Template:Mvar, we can define a continuum <math>(E_{v,c})_{c\in\mathbb{R}}</math> of affine hyperplanes with normal vector Template:Mvar: <math>E_{v,c}=\{x\in\mathbb{R}^n\colon x_1v_1+\ldots+x_nv_n=c\}</math> for <math>c\in\mathbb{R}</math>. For each <math>c\in\mathbb{R}</math>, we call the space <math>E^+_{v,c}=\{x\in\mathbb{R}^n\colon x_1v_1+\ldots+x_nv_n>c\}</math> the "positive side" of <math>E_{v,c}</math>, which is the side pointed to by the vector Template:Mvar. By the intermediate value theorem, every family of such hyperplanes contains at least one hyperplane that bisects the bounded set Template:Math: at one extreme translation, no volume of Template:Math is on the positive side, and at the other extreme translation, all of Template:Math's volume is on the positive side, so in between there must be a closed interval Template:Math of possible values of <math>c\in\mathbb{R}</math>, for which <math>E_{v,c}</math> bisects the volume of Template:Math. If Template:Math has volume zero, we pick <math>c=0</math> for all <math>v\in S</math>. Otherwise, the interval Template:Math is compact and we can canonically pick <math>c=\frac12(\inf I_v+\sup I_v)</math> as its midpoint for each <math>v\in S</math>. Thus we obtain a continuous function <math>\alpha\colon S\to\mathbb{R}</math> such that for each point Template:Mvar on the sphere Template:Mvar the hyperplane <math>E_{v,\alpha(v)}</math> bisects Template:Math. Note further that we have <math>I_{-v}=-I_v</math> and thus <math>\alpha(-v)=-\alpha(v)</math> for all <math>v\in S</math>.

Now we define a function <math>f\colon S\to\mathbb{R}^{n-1}</math> as follows:

<math>f(v)=(vol(A_1\cap E^+_{v,\alpha(v)}),\ldots,vol(A_{n-1}\cap E^+_{v,\alpha(v)}))</math>.

This function Template:Mvar is continuous (which can be proven with the dominated convergence theorem). By the Borsuk–Ulam theorem, there are antipodal points <math>v</math> and <math>-v</math> on the sphere Template:Mvar such that <math>f(v)=f(-v)</math>. Antipodal points correspond to hyperplanes <math>E_{v,\alpha(v)}</math> and <math>E_{-v,\alpha(-v)}=E_{-v,-\alpha(v)}</math> that are equal except that they have opposite positive sides. Thus, <math>f(v)=f(-v)</math> means that the volume of Template:Math is the same on the positive and negative side of <math>E_{v,\alpha(v)}</math>, for <math>i=1,\ldots,n</math>. Thus, <math>E_{v,\alpha(v)}</math> is the desired ham sandwich cut that simultaneously bisects the volumes of Template:Math.

Measure theoretic versionsEdit

In measure theory, Template:Harvtxt proved two more general forms of the ham sandwich theorem. Both versions concern the bisection of Template:Mvar subsets Template:Math of a common set Template:Mvar, where Template:Mvar has a Carathéodory outer measure and each Template:Math has finite outer measure.

Their first general formulation is as follows: for any continuous real function <math>f \colon S^n \times X \to \mathbb{R}</math>, there is a point Template:Mvar of the Template:Mvar-sphere Template:Math and a real number s₀ such that the surface Template:Math divides Template:Mvar into Template:Math and Template:Math of equal measure and simultaneously bisects the outer measure of Template:Math. The proof is again a reduction to the Borsuk-Ulam theorem. This theorem generalizes the standard ham sandwich theorem by letting Template:Math.

Their second formulation is as follows: for any Template:Math measurable functions Template:Math over Template:Mvar that are linearly independent over any subset of Template:Mvar of positive measure, there is a linear combination Template:Math such that the surface Template:Math, dividing Template:Mvar into Template:Math and Template:Math, simultaneously bisects the outer measure of Template:Math. This theorem generalizes the standard ham sandwich theorem by letting Template:Math and letting Template:Math, for Template:Math, be the Template:Mvar-th coordinate of Template:Mvar.

Discrete and computational geometry versionsEdit

File:Discrete ham sandwich cut.svg

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

In discrete 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 Template:Mvar points in the plane, each colored "red" or "blue", find a ham sandwich cut for them. First, Template:Harvtxt 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, Template:Harvtxt gave an algorithm for the general two-dimensional case; the running time of their algorithm is Template:Math, where the symbol Template:Mvar indicates the use of Big O notation. Finally, Template:Harvtxt found an optimal Template:Math-time algorithm. This algorithm was extended to higher dimensions by Template:Harvtxt where the running time is <math>o(n^{d-1})</math>. Given Template:Mvar sets of points in general position in Template:Mvar-dimensional space, the algorithm computes a Template:Math-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. If Template:Mvar 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 Template:Harvtxt.

Generalization to algebraic surfacesEdit

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

Given <math>\binom{k+n}{n}-1</math> measures in an Template:Mvar–dimensional space, there exists an algebraic surface of degree Template:Mvar which bisects them all. (Template:Harvtxt).

This generalization is proved by mapping the Template:Mvar–dimensional plane into a <math>\binom{k+n}{n}-1</math> dimensional plane, and then applying the original theorem. For example, for Template:Math and Template:Math, the 2–dimensional plane is mapped to a 5–dimensional plane via:

Template:Math.