3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.