8
$\begingroup$

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.

  • 0
    I suppose all the ellipsoids are centered on the origin. Right?2012-09-11
  • 0
    @becko: It does not matter where the ellipsoids are placed in space, but how they are arranged. For example, two ellipsoids can be placed anywhere, but depending on how you arrange them the number of regions you obtain is different. If the do not intersect you obtain 3 regions, if they intersect in a circle 4 regions, if they intersect in a circle and a point 5 regions, and finally if they intersect in two ellipses 6 regions, which is the maximum.2012-09-11
  • 1
    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.2012-09-11
  • 0
    @John When I was reading your question I missed the word **maximum**. Sorry about that.2012-09-11
  • 1
    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?2012-09-11
  • 1
    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.)2012-09-17
  • 1
    @mjqxxxx I think the idea is that the ellipsoids _are_ allowed to have arbitrary sizes and eccentricities.2012-09-17
  • 0
    John: it's still not clear how you get even six regions, let alone 8; the point is that it's not obvious that connectivity is broken on _both_ ellipsoids in an intersecting configuration. It would help if you could give specific equations for the ellipsoids you believe divide space into eight regions, and better yet equations for the variety that makes up their intersection 'frame'.2012-09-17
  • 1
    @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?2012-09-17
  • 0
    @John Yep, looking at that I agree - the intersections are along the planes $y=\pm x$ and so the regions are the four 'arms' of the ellipsoids, the region in the middle and the region external to both ellipsoids. I'm substantially less sold on the eight regions, though; this six-region configuration looks at first glance as though it can only happen in specially constructed symmetric configurations. I'll try to look at a specific L-shaped case and see what the intersection region is but I don't think you can actually get the 'bulges' you're after.2012-09-17
  • 0
    Concerning the asymptotic complexity of $O(n^3)$, see also the MO question [Cylinders dividing $\mathbb{R}^3$](http://mathoverflow.net/questions/107285/cylinders-dividing-mathbbr3/107297#107297)2012-09-19

1 Answers 1

1

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.

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)Three ellipsoids

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.