I would like to know the generalized proof of this result: http://mathworld.wolfram.com/SpaceDivisionbySpheres.html, for $d$ dimensions. What is the maximum number of regions divided by $n$ hyperspheres in $R^d$? If I can't get an exact answer, an asymptotic answer would be nice.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
The answer is $$R_d(n) = \dbinom{n-1}{d} + \sum_{k=0}^d \dbinom{n}{k}.$$
I use an argument similar to the argument for hyperplanes instead of hyperspheres.
For $d = 2$, the answer is $n^2 - n + 2$ (for the proof of this, refer elsewhere). One can verify that $R_2(n) = n^2 - n + 2$.
Now for any formula $F_d(n)$ that represents the maximum number of regions divided by $n$ hyperspheres in $\mathbb{R}^d$, observe that $$F_d(n) = F_d(n-1) + F_{d-1}(n-1).$$
To see why this is true, imagine taking $n−1$ hyperspheres in $d$ dimensional space, then add the $n$th hypersphere to the group. The $n$th hypersphere meets the $n-1$ others at $d-1$-dimensional hyperspheres. Hence, the surface of the $n$'th hypersphere will be divided into $F_{d-1}(n-1)$ pieces, each surface generating an additional region.
It remains to prove that $R_d(n)$ satisfies the above recurrence. It indeed does; the details are left to the reader (hint: use Pascal's identity).
