9
$\begingroup$

If you place $n$ unit spheres in $\mathbb{R}^3$, then the number of regions formed by the intersection of the spheres should be bounded above by $n^3$.

This is something that a book handwaved as "easy to show", but I can't get a handle on how to prove this.

It's possible to place 4 unit spheres in a configuration like a tetrahedron to get $2^4 = 16$ regions, but beyond that, we can't place another unit sphere that intersects every single region. Of course, 16 is well below $4^3 = 64$. The bound of $n^3$ only becomes nontrivial at $n = 10$, because $2^{10} > 10^3$. I don't know how I would begin counting the number of regions that each new unit sphere can intersect to create new regions.

$\endgroup$
  • $\begingroup$ Just an idea: I'd try to treat this a bit like the Euler characteristic: count vertices where 3 spheres intersect, arcs where two intersect, spherical surface patches not intersecting any other spheres, and regions bounded by these. That forms a 3d CW complex, and you should be able to cancel things against one another. In the end, it might boil down to some upper bound on the number of vertices, which should be $V\le2\binom n3<\frac{n^3}3$. Haven't worked out all the details, though. $\endgroup$ – MvG Feb 12 '15 at 20:55
3
+50
$\begingroup$

Claim 1: $n\ge1$ circles drawn on a sphere divide the sphere into at most $n(n-1)+2$ regions.

Proof: For $n=1$ this is obvious. Suppose we have $k-1$ circles , and investigate what happens when you draw a new circle $c$. The new circle $c$ may intersect the previous circles at no more than $2(k-1)$ points; so the previous circles divide $c$ into at most $2(k-1)$ arcs. Each of these arc split a region in two. So the increase in the number of regions will be at most $2(k-1)$; the total number of regions cannot exceed $2+\sum\limits_{k=2}^n 2(k-1)=n(n-1)+2$.

The proof shows that this bound is sharp; if every two circles intersect and the intersection points do not collide then we have exactly $k(k-1)+2$ regions.

Claim 2: $n$ spheres divide the space into at most $2+\sum\limits_{k=2}^{n} \big((k-1)(k-2)+2\big)= \frac{n^3-3n^2+8n}3$ regions.

(You can repeat the same proof.)

$\endgroup$
2
$\begingroup$

The maximum number of regions formed by an arrangement of $d$-dimensional hyperspheres is

$$ R_d(n) = {n-1 \choose d} + \sum_{k=0}^{d} {n \choose k}$$

When we add the $n$th sphere $s_n$, each region either stays the same or is bisected (creating two regions). Thus the total number of regions $R_d(n)$ is the number of previous regions $R_d(n-1)$ plus the number of previous regions that are bisected $R_{d-1}(n-1)$. To explain the second term, suppose we are in dimension three. The intersection of $s_n$ with $s_{i<n}$ is at most $n-1$ circles on $s_n$. The regions on $s_n$ formed by these circles are the region bisectors and the maximum number of them is just the the dimension-reduced problem $R_2(n-1)$. In general,

$$ R_d(n) = R_d(n-1) + R_{d-1}(n-1) $$

The first equation then follows by induction. Note that these values agree with those proved by @user141614.

$$ \begin{array} ( R_2(n) &= n^2 - n + 2 \\ R_3(n) &= \frac{n^3 + 3n^2 + 8n}{3} \end{array} $$

$\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.