Abstract.
We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder.
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received May 23, 1997, and in revised form October 20, 1997.
Rights and permissions
About this article
Cite this article
Agarwal, P., Aronov, B. & Sharir, M. Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions. Discrete Comput Geom 21, 373–388 (1999). https://doi.org/10.1007/PL00009427
Issue Date:
DOI: https://doi.org/10.1007/PL00009427