# Ham-sandwich theorem

Stone–Tukey theorem

For any collection of three solids in the three-dimensional space $\mathbf R ^ {3}$ there exists a plane $L$ which simultaneously bisects all of them, i.e. divides each of the solids into two halfs of equal volume. In a popular form this result is stated as the fact that it is possible to cut fairly an open ham-sandwich consisting of two pieces of bread and a piece of ham with a single straight cut. More generally, for a collection of $d$ measurable sets (mass distributions, finite sets) in $\mathbf R ^ {d}$ there exists a hyperplane $H$ simultaneously bisecting all of them.

The ham-sandwich theorem is a consequence of the well-known Borsuk–Ulam theorem, which says that for any continuous mapping $f : {S ^ {d} } \rightarrow {\mathbf R ^ {d} }$ from a $d$- dimensional sphere $S ^ {d}$ into $\mathbf R ^ {d}$, there exists a pair of antipodal points $\{ v, - v \} \subset S ^ {d}$ such that $f ( - v ) = f ( v )$. (Cf. also Antipodes.)

Other examples of combinatorial partitions of masses include the "centre-point theorem" and the related "centre-transversal theorem" , equi-partitions of masses by higher-dimensional "orthants" , equi-partitions by convex cones, partitions of lines and other geometric objects, etc.

The centre-point theorem says that for any measurable set in $A \subset \mathbf R ^ {d}$ there exists a point $x \in \mathbf R ^ {d}$ such that for any half-space $P \subset \mathbf R ^ {d}$: if $x \in P$ then

$${ \mathop{\rm vol} } ( P \cap A ) \geq { \frac{1}{d + 1 } } { \mathop{\rm vol} } ( A ) .$$

The centre-transversal theorem, [a5], is a generalization of both the ham-sandwich and the centre-point theorem and it claims that for any collection $A _ {0} \dots A _ {k}$, $0 \leq k \leq d - 1$, of Lebesgue-measurable sets in $\mathbf R ^ {d}$( cf. also Lebesgue measure) there exists a $k$- dimensional affine subspace $D \subset \mathbf R ^ {d}$ such that for every closed half-space $P$ and every $i$: if $D \subset P$ then

$$\mu ( A _ {i} \cap P ) \geq { \frac{1}{d - k + 1 } } \mu ( A _ {i} ) .$$

An example of an equi-partition result into higher-dimensional "orthants" is as follows, [a3]. Any measurable set $A \subset \mathbf R ^ {5}$ can be partitioned into $16$ pieces of equal measure by $4$ hyperplanes.

The proofs of all these and other related results are topological and use several forms of generalized Borsuk–Ulam-type theorems, see [a2], [a4], [a6].

The ham-sandwich theorem, together with other relatives belonging to combinatorial (equi)partitions of masses, has been often applied to problems of discrete and computational geometry, see [a5] for a survey.