On lines avoiding unit balls in three dimensions


Journal Article

Let B be a set of n unit balls in ℝ3. We show that the combinatorial complexity of the space of lines in ℝ3 that avoid all the balls of B is O(n3+ε), for any ε > 0. This result has connections to problems in visibility, ray shooting, motion planning and geometric optimization.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2004

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 36 - 45

Digital Object Identifier (DOI)

  • 10.1145/997817.997826

Citation Source

  • Scopus