On lines avoiding unit balls in three dimensions

Published

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.

Duke Authors

Cited Authors

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

Published Date

  • September 29, 2004

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 36 - 45

Citation Source

  • Scopus