Line transversals of balls and smallest enclosing cylinders in three dimensions


Journal Article

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.

Duke Authors

Cited Authors

  • Agarwal, PK; Aronov, B; Sharir, M

Published Date

  • January 1, 1997

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 483 - 492

Citation Source

  • Scopus