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. © Springer 2005.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2005

Published In

Volume / Issue

  • 34 / 2

Start / End Page

  • 231 - 250

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/s00454-005-1166-2

Citation Source

  • Scopus