Lines Avoiding Unit Balls in Three Dimensions

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

Authors and Affiliations

1. Department of Computer Science, Duke University, Durham, NC 27708-0129, USA

   Pankaj K. Agarwal, Boris Aronov & Vladlen Koltun

2. School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA

   Micha Sharir

Corresponding authors

Correspondence to Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun or Micha Sharir.

Reprints and permissions