Skip to main content
1 of 3
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

This non-answer completes Joseph O'Rourke's nice non-answer, for the case of $n$ hyperplanes in $\mathbb{R}^d$ in general position. But it also suggests that the OP situation may also well have unique answers.

Define:

$U_{d,n}=$ number of unbounded regions cut by $n$ hyperplanes in $\mathbb{R}^d$

$B_{d,n}=$ number of bounded regions

$T_{d,n}=$ total number of unbounded regions $=U_{d,n}+B_{d,n}$

$S_{d,n}=$ number of regions cut on the sphere $S^d$ by $n$ great $S^{d-1}$-circles

Then $U_{d,n}, B_{d,n}$, $T_{d,n}$ and $S_{d,n}$ are unique with these formulas:

$U_{d,0}=1$, $\quad B_{d,0}=0$, $\quad T_{d,0}=1$, $\quad S_{d,0}=1$

$U_{1,n}=2$, $\quad B_{1,n}=n-1$, $\quad T_{1,n}=n+1$

and for $n>0$

  1. $U_{d+1,n}=S_{d,n}$
  2. $S_{d,n}=U_{d,n}+2B_{d,n}$
  3. $T_{d,n+1}=T_{d,n}+\sum_{i=0}^{i=d-1}{n\choose i}$

Proof.

  1. In $\mathbb{R}^{d+1}$ take a huge and growing $S^d$ sphere, so that all the bounded regions zoom down to a point at the center of the sphere, the hyperplanes become great circles on the sphere and the unbounded regions corresponds to regions cut by the circles on the sphere. Therefore if the numbers are unique (as will be proved at the end) 1. follows.

  2. Centrally project $\mathbb{R}^d$ onto a half $S^d$ (tangent to it). Complete the semisphere to a sphere by central symmetry. Then the hyperplanes become great circles, the $B_{d,n}$ bounded regions in $\mathbb{R}^d$ become $2B_{d,n}$ regions in $S^d$ and the $U_{d,n}$ unbounded ones become $U_{d,n}$ regions stretching across the suture line (equator) of the sphere. Again by unicity 2. follows.

  3. Start with $\mathbb{R}^d$ and $n$ hyperplanes in generic position inside it. Now add a new hyperplane in generic position the following way: first chose a point inside one region: no matter how that point is eventually stretched to a hyperplane, to it will split the region in two, for a gain of 1, or $n \choose 0$. Now stretch that point to a line: since it is a generic line it will meet each of the $n$ hyperplanes once and at each meeting the line will cross into one one new region and split it - with a gain of $n \choose 1$ new regions. Next stretch the line to a generic 2-plane, which will meet once each of the $(d-2)$-dimensional intersections of two hyperplanes; at each meeting the growing plane will arrive from having already crossed 3 of the 4 regions, to cross into the fourth and cut it; this a gain of another $n \choose 2$ regions. In general as a generic $m-1$-plane grows to a generic $m$-plane it will meet all the $n \choose m$ $(n-m)$-dimensional intersections of $m$ hyperplanes, and each time it will go from cutting $2^m-1$ regions before crossing the intersection to cutting all $2^m$ after crossing, for a total gain of $n \choose m$ regions. This continues up to $m=d-1$, proving 3.

Proof of Unicity.

By induction:

$U_{d,0}$, $\quad B_{d,0}$, $\quad T_{d,0}$, $\quad S_{d,0}$ are unique;

$T_{d,n}$ unique $\implies$ $T_{d,n+1}$ unique (by the proof of 3.);

$U_{d,n}$ and $B_{d,n}$ unique $\implies$ $S_{d,n}$ unique (by the proof of 2. and the fact that the construction can be reversed in a non-unique way to show that $S_{d,n}=U_{d,n}+2B_{d,n}$ for some values of $U_{d,n}$ and $B_{d,n}$);

$S_{d,n}$ unique $\implies$ $U_{d+1,n}$ unique (by the proof of 1.);

$U_{d+1,n}$ and $T_{d+1,n}$ unique $\implies$ $B_{d+1,n}$ unique (as $B=T-U$).

Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43