# An upper bound on the number of regions in $\mathbb{R}^3$ from the interection of unit spheres

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.

• 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. – MvG Feb 12 '15 at 20:55

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

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}$$