Lines avoiding unit balls in three dimensions

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)231-250
    Number of pages20
    JournalDiscrete and Computational Geometry
    Issue number2
    StatePublished - Aug 2005

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics


    Dive into the research topics of 'Lines avoiding unit balls in three dimensions'. Together they form a unique fingerprint.

    Cite this