Lines avoiding unit balls in three dimensions

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

    Research output: Contribution to journalArticle


    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

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

  • Cite this

    Agarwal, P. K., Aronov, B., Koltun, V., & Sharir, M. (2005). Lines avoiding unit balls in three dimensions. Discrete and Computational Geometry, 34(2), 231-250.