Cylinders dividing $\mathbb{R}^{3}$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T00:31:14Z http://mathoverflow.net/feeds/question/107285 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107285/cylinders-dividing-mathbbr3 Cylinders dividing $\mathbb{R}^{3}$ VCF 2012-09-15T20:05:55Z 2012-09-20T02:00:02Z <p>Consider $n$ affine copies of a compact cylinder, say $S^{1}\times [-3,3]$ with top and botom, sitting inside $\mathbb{R}^{3}$. </p> <p>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.</p> <p>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?</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/107285/cylinders-dividing-mathbbr3/107295#107295 Answer by Gerhard Paseman for Cylinders dividing $\mathbb{R}^{3}$ Gerhard Paseman 2012-09-15T23:24:01Z 2012-09-15T23:24:01Z <p>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.</p> <p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.09.15</p> http://mathoverflow.net/questions/107285/cylinders-dividing-mathbbr3/107297#107297 Answer by Joseph O'Rourke for Cylinders dividing $\mathbb{R}^{3}$ Joseph O'Rourke 2012-09-16T00:42:23Z 2012-09-16T00:48:00Z <p>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," <em>Discrete &amp; Computational Geometry</em>, Volume 45, Issue 1, January 2011, Pages 45-64 (<a href="http://dl.acm.org/citation.cfm?id=1929932" rel="nofollow">ACM link</a>; <a href="http://www.cims.nyu.edu/~esther/Publications/cylinders.pdf" rel="nofollow">PDF download link</a>). From the Abstract:</p> <blockquote> <p>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 ...</p> </blockquote> <p>Deeper into the paper:</p> <blockquote> <p>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).</p> </blockquote> <p><br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/Cylinders3D.jpg" alt="Fig. 1a"><br /> 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 <em><a href="http://cs.smith.edu/~orourke/books/discrete.html" rel="nofollow">The Handbook of Discrete and Computational Geometry</a></em>, Theorem 24.1.4, in a chapter by Dan Halperin.</p> <p>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.</p> http://mathoverflow.net/questions/107285/cylinders-dividing-mathbbr3/107640#107640 Answer by Joseph O'Rourke for Cylinders dividing $\mathbb{R}^{3}$ Joseph O'Rourke 2012-09-20T02:00:02Z 2012-09-20T02:00:02Z <p>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. <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/EllipsoidsX.jpg" alt="Ellipsoids Crossing"><br /> But I may well be misinterpreting the intent...</p>