Line transversals of balls and smallest enclosing cylinders in three dimensions
Pankaj K. Agarwal, Boris S. Aronov, Micha Sharir · 1997
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. 1 Introduction Line transversals in three dimensions. Let S be a collection of n compact convex sets with non-empty interiors in R 3 . A line ` is called a (line) transversal of S if it intersects every member of S. Let T (S) denote the set of all line transversals of S. Since lines in 3space can be parametrized by 4 real parameters, T (S) is a 4-dimensional set. For example, one may use the parameterization (¸ 1 ; ¸ 2 ; ¸ 3 ; ¸ 4 ), where the equations of the line are given by y = ¸ 1 x + ¸ 2 , z = ¸ 3 x + ¸ 4 ; this excludes lines parallel to the yz-plan...