Line transversals of balls and smallest enclosing cylinders in three dimensions
Published
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.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Aronov, B; Sharir, M
Published Date
- January 1, 1999
Published In
Volume / Issue
- 21 / 3
Start / End Page
- 373 - 388
International Standard Serial Number (ISSN)
- 0179-5376
Digital Object Identifier (DOI)
- 10.1007/PL00009427
Citation Source
- Scopus