6
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ This is likely not of interest to you, but general theorems from the theory of arrangements of surfaces indicate that, asymptotically, the number of regions is $O(n^3)$. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 15, 2012 at 20:43
  • $\begingroup$ Thank you, I didn´t kow that. It makes sense to me since, for example, I know that if we consider $n$ planes instead of cylinders we get at most $(n^3+5n+6)/6$ regions. $\endgroup$
    – Victor
    Commented Sep 15, 2012 at 20:49
  • $\begingroup$ Does the cylinder have a top and bottom on it? $\endgroup$
    – Ben McKay
    Commented Sep 15, 2012 at 20:54
  • $\begingroup$ VCF -- don't you in fact consider infinite (i.e., non-compact) round cylinders? Standardly embedded $S^1\times [-3,3]$ does not subdivide $\mathbb{R}^3$ at all. $\endgroup$
    – algori
    Commented Sep 15, 2012 at 20:55
  • 1
    $\begingroup$ algori: Standardly embedded $S^1\times [-3,3]$, together with top and bottom, has an inside and an outside. (At least that's how I interpreted "with top and bottom", though it would be good for the OP to make this clearer.) $\endgroup$
    – Steven Landsburg
    Commented Sep 15, 2012 at 21:31

3 Answers 3

Reset to default
8
$\begingroup$

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


         Fig. 1a
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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I still have concerns, but they may be illfounded. It looks like helical cylinders will not be defined by finitely many algebraic surface patches. Thank you for expanding on this, and do not be distressed by my reservations and contrary position. Gerhard "Gaining Some Expertise Each Day" Paseman, 2012.09.15 $\endgroup$
    – Gerhard Paseman
    Commented Sep 16, 2012 at 2:40
  • 1
    $\begingroup$ In the first quote, the combinatorial complexity is $v+e+f$ on the boundary of the union of solid cylinders, not the number of regions formed by their surfaces. There can be $\omega(n^3)$ regions from infinite hollow cylinders, or any smooth surface, since there can be that many bounded regions from planes (as in the coins configuration). $\endgroup$
    – Douglas Zare
    Commented Sep 16, 2012 at 2:57
  • $\begingroup$ @Joseph: It would be nice to have the kind of closed formula I am looking for. But the asymtotic complexity point of view makes me think that perhaps it isn´t necessary to have one. $\endgroup$
    – Victor
    Commented Sep 16, 2012 at 12:35
  • $\begingroup$ @Douglas: You are absolutely right. I stand corrected---Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Sep 16, 2012 at 12:38
  • $\begingroup$ Oops, I meant $\Omega(n^3)$ not $\omega(n^3)$ above. $\endgroup$
    – Douglas Zare
    Commented Sep 16, 2012 at 13:27
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Another motivating example is to use two helical cylinders. I doubt that such a shape could be produced from a finite arrangement of regular cylinders, but if it could, the potential for growing the number of regions is (in my view) dramtically increased. Gerhard "Ask Me About Twisty Thinking" Paseman, 2012.09.15 $\endgroup$
    – Gerhard Paseman
    Commented Sep 15, 2012 at 23:33
  • 2
    $\begingroup$ @Gerhard: I believe one can partition an end-capped cylinder into four surface patches that meet the criteria I now set out more clearly in my posting. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 16, 2012 at 0:45
  • $\begingroup$ @Gerhard: This is just my mind wondering, but if we have two ellipsoids of the same size I think we can arrange arrange them so that we get 8 regions. First make a perfect cross (this yiels 6 regions) and then slide the vertical ellipsoid to the right so that two mnew patches appear thus yielding 2 more regions. What do you think? $\endgroup$
    – Victor
    Commented Sep 19, 2012 at 11:39
  • $\begingroup$ VCF: I think you should ask Joseph's help with this one. The cylinder one was easy because I could start with two unit cylinders to get 10 regions, and then lengthen each. For the ellipsoids, I can't do that. I think 6 is the most, but Joseph has programs that can likely resolve this for you. Gerhard "My Thinking Isn't That Twisty" Paseman, 2012.09.19 $\endgroup$
    – Gerhard Paseman
    Commented Sep 19, 2012 at 20:44
0
$\begingroup$

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.
         Ellipsoids Crossing
But I may well be misinterpreting the intent...

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, I was wrong. Certainly 6 is the most with two. I had gotten the same picture with Maple. $n$ ellipsoids of any size will divide space into the maximum number of regions if any two intersect in two ellipses as the two in your configuration (i.e. in two points), any three in 8 points and any four or more have empty intersection. Roughly speaking, you may think of this conditions as happening when the defining equations are "linearly independent". The max is $n(4n^2-9n+11)/3$. I give you -1 as your answer is not related to the original question and because of the ambiguous final remark $\endgroup$
    – Victor
    Commented Sep 20, 2012 at 12:06
  • $\begingroup$ Given the trouble Joseph has taken to help (and to further the spirit of contention), I disagree with your downvote, VCF. I will return to this later today with my voting account and give it my seventh (sixth?) vote. Gerhard "Miss Manners Might Also Disapprove" Paseman, 2012.09.20 $\endgroup$
    – Gerhard Paseman
    Commented Sep 20, 2012 at 16:07
  • $\begingroup$ @Gerhard: It´s fine you disagree. Joseph has certainly shown good effort. I voted up his first answer and acepted it. But I stand by my opinion that it is good practice to write answers that address the question somehow, not simply the comments. It has nothing to do with manners. $\endgroup$
    – Victor
    Commented Sep 20, 2012 at 16:45
  • $\begingroup$ @VCF: I think the situation is more complex than that. However, I will cast my vote and then move on. I have learned that Joseph is rather unaffected by the vote, and I appreciate the opportunity to contribute to the question and to disagree with each of you and Joseph. I look forward to more questions as well as more progress on this question. Gerhard "Agreeing To Disagree Agreefully; Agreed?" Paseman, 2012.09.20 $\endgroup$
    – Gerhard Paseman
    Commented Sep 20, 2012 at 21:18
  • $\begingroup$ There. Sixth vote done. Gerhard "Ask Me About System Design" Paseman, 2012.09.20 $\endgroup$
    – Gerhard Paseman
    Commented Sep 21, 2012 at 5:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .