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