Euler's Formula, Proof 16: Binary Space Partition

A binary space partition is a data structure commonly used for computer graphics and other geometric searching problems. It's formed by cutting space by a hyperplane, then recursively partitioning each of the two resulting halfspaces. The result is a hierarchical decomposition of space into convex cells.

In 1974, Helge Tverberg showed that, given any convex polytope $K$ , one can find a binary space partition that decomposes $K$ into simplices. This is obvious for two dimensional polytopes (just repeatedly cut along polygon diagonals); the general proof proceeds by induction on dimension and number of faces:

We assume $K$ is not a simplex or we would already be done.

If $K$ has a vertex $P$ incident to more than $d$ facets, then (by induction on dimension) we can partition $K$ by hyperplanes through $P$ into smaller polytopes each of which has exactly $d$ facets incident to $P$ . The number of facets not incident to $P$ in each of these polytopes is at most the same as in $K$ , so each smaller polytope has fewer facets than $K$ . By induction on number of facets, we can recursively partition the smaller polytopes into simplices.

On the other hand suppose that each vertex of $K$ has only $d$ incident facets. Let $P$ be a vertex of $K$ that is not adjacent to some two facets $F_{1}$ and $F_{2}$ (we can find $P$ , $F_{1}$ , and $F_{2}$ by induction on dimension if $K$ has a non-simplicial facet; if all facets of $K$ are simplices, let $F_{1}$ and $F_{2}$ be two adjacent facets and $P$ be any vertex other than the $d + 1$ vertices shared by $F_{1}$ and $F_{2}$ ). Let $L$ be the hyperline contained in the hyperplanes through $F_{1}$ and $F_{2}$ , and cut $K$ by a hyperplane through $P$ and $L$ . Then each of the two pieces avoids one of the facets $F_{i}$ , but has a new facet on the cut plane, so its number of facets is not increased. One can show that each piece either has more than $d$ facets at $P$ (in which case we can apply the previous case), or avoids an additional facet of $K$ (in which case we can apply induction on the number of facets), so either way we can partition each piece recursively.

The number of cuts in this partition may be exponential in the number of facets, but this seems unavoidable due to examples like the hypercube which have few facets but require many cuts.

Tverberg then proves that the Euler characteristic $χ (K)$ (as defined more precisely for the shelling proof) is always zero, by induction on dimension and on the number of cuts in the binary space partition:

If $K$ is a simplex, the number of faces of any dimension is counted by a binomial coefficient, and the identity $χ (K) = 0$ is just the application of the binomial theorem to the evaluation of $(1 + x)^{d}$ at $x = - 1$ .

Otherwise, let the top level cut of the binary space partition split $K$ into two polytopes $K_{1}$ and $K_{2}$ . Let $K_{3}$ be the convex hull of the set of vertices of $K$ that are contained in the cutting hyperplane, and let $K_{4}$ be the intersection of $K$ with the cutting hyperplane. Then we have the formula $χ (K) = χ (K_{1}) + χ (K_{2}) + 2 χ (K_{3}) - 3 χ (K_{4}),$ since each face of $K$ is either contained in the cutting hyperplane (contributing to all four terms $χ (K_{i})$ , split by the cutting hyperplane (forming a face of one lower dimension in $K_{1}$ , $K_{2}$ , and $K_{4}$ , and contributing a negated term to each of these three polytopes' Euler characteristics), or is contained in one of the two halfspaces (and contributes only to $χ (K_{1})$ or $χ (K_{2})$ .

$K_{1}$ and $K_{2}$ have smaller binary space partitions, and $K_{3}$ and $K_{4}$ have lower dimension, so by induction all have zero Euler characteristic. Therefore, $χ (K)$ is also zero.

Proofs of Euler's Formula.
From the Geometry Junkyard, computational and recreational geometry pointers.
David Eppstein, Theory Group, ICS, UC Irvine.