# Into how many parts do $n$ ellipsoids divide $\mathbb{R}^{3}$?

What is the maximum number of regions into which $\mathbb{R}^{3}$ can be divided by $n$ ellipsoids? (Each ellipsoid has the same size). Let´s denote this number by $r_{n}$.

Clearly $r_{1}=2$. But even with two ellipsoids things get complicated: Certainly $r_{2}\ge 6$ (e.g. $x^2+(y/2)^2+z^2$ and $x^2+y^2+(z/2)^2$), and I think that 6 is the maximum.

Note that $r_{3}\ge 14$ because it is possible to draw three ellipses dividing the plane into 14 regions. More generally $$r_{n}\ge 2n^{2}-2n+2,$$ since $n$ ellipses divide the plane into at most $2n^{2}-2n+2$ regions, and this happens if and only if any two ellipses intersect in 4 points and any three have empty intersection (Check this, and also this post has a related question).

Note that $n$ circles (resp. ellipses) (resp. equilateral triangles) divide the plane into at most $n^2-n+2$ (resp. $2n^2-2n+2$) (resp. $3n^2-3n+2$) regions. Note that for $n\ge 1$ $n^2-n+2\le 2n^2-2n+2\le 3n^2-3n+2$. It seems that this situation generalizes to higher dimensions. That is, the maximum number of regions into which 3-space can be divided by $n$ ellipsoids lies above the corresponding number for spheres and below the corresponding number for regular tetrahedra (i.e. each of the four faces is an equilateral triangle).

Now, $n$ spheres divide 3-space into at most $n(n^2-3n+8)/3$ regions. But what is the maximum number of regions into which 3-space can be divided by $n$ regular tetrahedra?

From the standpoint of asymptotic complexity $r_{n}=\mathcal{O}(n^{3})$, as it is indicated by general theorems from the theory of arrangements of surfaces.

-
I think your formula is incorrect even in the case $n=2$. Two ellipsoids can divide three-space into five regions. I'm assuming that the "outside" region (the unbounded one) counts as one of the regions. –  bubba Sep 11 '12 at 11:26
It would help if you told us how you derived these formulas. Also, can you describe the configuration of two ellipses that yields six regions? –  Rahul Sep 11 '12 at 22:13
Would the answer be different if the ellipsoids were allowed to have different sizes and/or eccentricities? That restriction adds some extra complexity. (For instance, the result might be a function of the eccentricity.) –  mjqxxxx Sep 17 '12 at 15:50
@mjqxxxx I think the idea is that the ellipsoids are allowed to have arbitrary sizes and eccentricities. –  Steven Stadnicki Sep 17 '12 at 17:29
@Steven Stadnicki: For example, take $x^{2}+(y^{2}/4)+z^{2}=1$ as your first ellipsoid. As your second ellipsoid take the previous one rotated 90 degrees about the $x$-axis. These two ellipsoids will intersect in two ellipses which in turn intersect in exactly two points: $(\pm 1,0,0)$ I think. This configuration yields 6 regions. Do you agree? –  John Sep 17 '12 at 18:58

I may be mistaken (i.e. criticism is very welcomed), but I think I was able to rigorously prove the following: Define two ellipses to be simply intersecting if they intersect in exactly two points. Then we say that two ellipsoids are simply intersecting if they intersect in two simply intersecting ellipses.

Proposition: Let $E$ be an arrangement of n ellipsoids in 3-space, let $N$ be the number of regions into which $E$ divides 3-space, and let $M=n(4n^{2}-9n+11)/3$. If

1. Any two ellipsoids in $E$ are simply intersecting, and
2. Any three ellipsoids in $E$ intersect in 8 points, and
3. Any four or more ellipsoids have empy intersection,

then $N=M$. Otherwise, $N<M$.

Very roughly speaking, If 1-3 hold, then we look at how one of the ellipsoids is divided into patches by the other $n-1$ ellipsoids,and see in which way each of these patches divides a region formed by the other $n-1$ ellipsoids. This gives us a way to count regions. If either of 1-3 fails then the a similar idea will yield less patches and hence less regions.

For example, $x^{2}+(y/4)^{2}+z^{2}=1$ (blue), $(x/4)^{2}+y^{2}+z^{2}=1$ (green), and $x^{2}+y^{2}+(z/4)^{2}=1$ (red) will yield the maximum (20 regions)

Note that linear independence of the defining equations is not sufficient to guarantee that the maximum number of regions is obtained. E.g. $(x/2)^2+(y/4)^2+z^2=1$, $(x/4)^2+y^2+(z/2)^2=1$ intersect in two disjoing ellipses, and yield only 5 regions.

The methods and ideas I have used also work in dimension 2, and I will probably add more later to this answer about the general case in dimension $\ge 4$. This will all be part of an upcoming paper.

-