Cylinders dividing $\mathbb{R}^{3}$ - MathOverflow

Cylinders dividing $\mathbb{R}^{3}$

2012-09-15T20:05:55Z

Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$.

For each $n$ we may ask ourselves how to arrange the $n$ cylinders so that they divide 3-space into the maximum number of regions possible. For example, one cylinder divides 3-space in two regions. Two cylinders, if we intersect them so as to make a cross, divide space in 6 regions, but maybe more is possible.

If $n\ge 3$ things start to get complicated. For example, if $n=3$ we can obtain 14 regions if we start with two cylinders making a cross and then intersect the last cylinder diagonally, but I am not sure that this is the maximum. Perhaps more is possible?

I would like to know if there is a general formula giving us the maximum number of regions into which 3-space can be divided by cylinders.

Fundamental concepts like homology or the Euler characteristic may be of help if applied appropriately. Thus, if there is a general theory studying these kind of question I would appreciate any references on the matter.

Answer by Gerhard Paseman for Cylinders dividing $\mathbb{R}^{3}$

2012-09-15T23:24:01Z

If we arrange two cylinders as a T or an L, I think one can get 7 or 8 regions with two cylinders. Also, if I have two n-gonal prisms sharing the same axis and the faces perpendicular to the axis are in the same two planes, I can still get better than 2n regions just with a small rotation.

Contrary to Joseph O'Rourke's comment (and with much less expertise than Joseph to back up my remarks), I think the geometry of surfaces will be insufficient, as I can take the 7 or 8 regions produced above, make a small rotation, and likely greatly increase the number of regions produced. There may be an eventual cubic upper bound, but I am not seeing it.

Gerhard "Ask Me About System Design" Paseman, 2012.09.15

Answer by Joseph O'Rourke for Cylinders dividing $\mathbb{R}^{3}$

2012-09-16T00:42:23Z

The definitive (and recent!) work on this topic, from the asymptotic complexity point of view (which I emphasized in my comment) is due to Esther Ezra, a student of Micha Sharir. See especially the paper from her Ph.D. thesis, "On the Union of Cylinders in Three Dimensions," Discrete & Computational Geometry, Volume 45, Issue 1, January 2011, Pages 45-64 (ACM link; PDF download link). From the Abstract:

We show that the combinatorial complexity of the union of $n$ infinite cylinders in $\mathbb{R}^3$, having arbitrary radii, is $O(n^{2+\epsilon})$, for any $\epsilon>0$; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir ...

Deeper into the paper:

We note that it is crucial to assume that the cylinders are inﬁnite. Otherwise, the combinatorial complexity of their union is $\Omega(n^3)$ in the worst case. Indeed, suppose we have a set of $n$ cylinders, each of which with a sufﬁciently large radius and height that is arbitrarily close to $0$. We can now arrange these cylinders in a (three-dimensional) grid-like structure, resulting in $\Omega(n^3)$ holes in the union; see Figure 1(a).

The general theorem I had in mind in my (hasty) comment is that, $n$ algebraic surface patches in $\mathbb{R}^d$ define an arrangement of combinatorial complexity of $O(n^d)$, where the constant of proportionality depends on $d$ and the maximum degree of the algebraic surfaces and of the polynomials defining their boundaries. This can be found on p.533 of The Handbook of Discrete and Computational Geometry, Theorem 24.1.4, in a chapter by Dan Halperin.

I believe a closed, end-capped, finite cylinder can be partitioned into four surface patches satisfying the preconditions of this theorem. So we should have $\Omega(n^3)$ from the coins example above, and $O(n^3)$ from this general theorem, and so $\Theta(n^3)$ asymptotically.

Answer by Joseph O'Rourke for Cylinders dividing $\mathbb{R}^{3}$

2012-09-20T02:00:02Z

This is an attempt to illustrate VCF's two crossing congruent ellipsoids (from comments to Gerhard), one of which is shifted slightly in the $+x$ direction. It appears to me the shifting joins the top and bottom regions of the vertical ellipsoid, and so reducing the number of regions rather than increasing them.

But I may well be misinterpreting the intent...