Abstract
We show that the combinatorial complexity of the union of n infinite cylinders in ℝ3, having arbitrary radii, is O(n 2+ε), for any ε>0; the bound is almost tight in the worst case, thus settling a conjecture of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), who established a nearly-quadratic bound for the restricted case of nearly congruent cylinders. Our result extends, in a significant way, the result of Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000), in particular, a simple specialization of our analysis to the case of nearly congruent cylinders yields a nearly-quadratic bound on the complexity of the union in that case, thus significantly simplifying the analysis in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000). Finally, we extend our technique to the case of “cigars” of arbitrary radii (that is, Minkowski sums of line-segments and balls) and show that the combinatorial complexity of the union in this case is nearly-quadratic as well. This problem has been studied in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000) for the restricted case where all cigars have (nearly) equal radii. Based on our new approach, the proof follows almost verbatim from the analysis for infinite cylinders and is significantly simpler than the proof presented in Agarwal and Sharir (Discrete Comput. Geom. 24:645–685, 2000).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, P.K., Pach, J., Sharir, M.: State of the union, of geometric objects: a review. In: Proc. Joint Summer Research Conference on Discrete and Computational Geometry—Twenty Years Later. Contemp. Math., vol. 452, pp. 9–48. AMS, Providence (2008)
Agarwal, P.K., Schwarzkopf, O., Sharir, M.: The overlay of lower envelopes and its applications. Discrete Comput. Geom. 15(1), 1–13 (1996)
Agarwal, P.K., Sharir, M.: Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions. Discrete Comput. Geom. 24, 645–685 (2000)
Aronov, B., Efrat, A., Koltun, V., Sharir, M.: On the union of κ-round objects in three and four dimensions. Discrete Comput. Geom. 36, 511–526 (2006)
Aronov, B., Sharir, M.: On translational motion planning of a convex polyhedron in 3-space. SIAM J. Comput. 26, 1785–1803 (1997)
Aronov, B., Sharir, M., Tagansky, B.: The union of convex polyhedra in three dimensions. SIAM J. Comput. 26, 1670–1688 (1997)
Boissonnat, J.D., Sharir, M., Tagansky, B., Yvinec, M.: Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom. 19, 485–519 (1998)
Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195–222 (1987)
Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387–421 (1989)
de Berg, M.: Improved bounds on the union complexity of fat objects. Discrete Comput. Geom. 40(1), 127–140 (2008)
de Berg, M.: Better bounds on the union complexity of locally fat objects. In: Proc. 26th Annu. Sympos. Comput. Geom., pp. 39–47 (2010)
Efrat, A.: The complexity of the union of (α,β)-covered objects. SIAM J. Comput. 34, 775–787 (2005)
Efrat, A., Katz, M.: On the union of α-curved objects. Comput. Geom. Theory Appl. 14, 241–254 (1999)
Efrat, A., Sharir, M.: On the complexity of the union of fat objects in the plane. Discrete Comput. Geom. 23, 171–189 (2000)
Ezra, E., Aronov, B., Sharir, M.: Improved bound for the union of fat triangles. In: Proc. 22nd Annu. ACM–SIAM Sympos. Discr. Alg. (to appear)
Ezra, E., Sharir, M.: Almost tight bound for the union of fat tetrahedra in three dimensions. J. ACM 57(1), 2 (2009)
Ezra, E., Sharir, M.: Counting and representing intersections among triangles in three dimensions. Comput. Geom. Theory Appl. 32, 196–215 (2005)
Halperin, D.: On the complexity of a single cell in certain arrangements of surfaces related to motion planning. Discrete Comput. Geom. 11, 1–33 (1994)
Halperin, D., Sharir, M.: Almost tight upper bounds for the single cell and zone problems in three dimensions. Discrete Comput. Geom. 14(4), 385–410 (1995)
Haussler, D., Welzl, E.: ε-nets and simplex range queries. Discrete Comput. Geom. 2, 127–151 (1987)
Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1, 59–71 (1986)
Koltun, V., Sharir, M.: The partition technique for overlays of envelopes. SIAM J. Comput. 32(4), 841–863 (2003)
Matoušek, J., Miller, N., Pach, J., Sharir, M., Sifrony, S., Welzl, E.: Fat triangles determine linearly many holes. In: Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pp. 49–58 (1991)
Matoušek, J., Pach, J., Sharir, M., Sifrony, S., Welzl, E.: Fat triangles determine linearly many holes. SIAM J. Comput. 23, 154–169 (1994)
Pach, J.: On the complexity of the union of geometric objects. Lect. Notes Comput. Sci. 2098, 292–307 (2001)
Pach, J., Safruti, I., Sharir, M.: The union of congruent cubes in three dimensions. Discrete Comput. Geom. 30, 133–160 (2003)
Pach, J., Tardos, G.: On the boundary complexity of the union of fat triangles. SIAM J. Comput. 31, 1745–1760 (2002)
Sharir, M., Agarwal, P.K.: Davenport–Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
Part of the work on this paper was performed at the Department of Computer Science, Duke University, Durham, NC 27708-0129, USA, and has been supported by NSF under grants CNS-05-40347, CFF-06-35000, and DEB-04-25465, by ARO grants W911NF-04-1-0278 and W911NF-07-1-0376, and by an NIH grant 1P50-GM-08183-01. A preliminary version of this paper has appeared in Proc. 49th Annu. IEEE Sympos. Found. Comput. Sci. 2008.
Rights and permissions
About this article
Cite this article
Ezra, E. On the Union of Cylinders in Three Dimensions. Discrete Comput Geom 45, 45–64 (2011). https://doi.org/10.1007/s00454-010-9312-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9312-x