Cutting triangular cycles of lines in space

Boris Aronov, Vladlen Koltun, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    We show that n lines in 3-space can be cut into O(n2-1/69 log16/69 n) pieces, such that all depth cycles defined by triples of lines are eliminated. This partially resolves a long-standing open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

    Original languageEnglish (US)
    Pages (from-to)231-247
    Number of pages17
    JournalDiscrete and Computational Geometry
    Issue number2
    StatePublished - Feb 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 'Cutting triangular cycles of lines in space'. Together they form a unique fingerprint.

    Cite this