Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions

Boris Aronov, Micha Sharir

    Research output: Contribution to journalArticle

    Abstract

    Given n pairwise disjoint non-vertical lines in 3-space, their vertical depth (i.e., above/below) relation may contain cycles. We show that the lines can be cut into O(n3/2polylogn) pieces, such that the depth relation among these pieces is a proper partial order. This bound is nearly tight in the worst case. Our proof uses a recent variant of the polynomial partitioning technique, due to Guth, and some simple tools from algebraic geometry. Our technique can be extended to eliminating all cycles in the depth relation among segments and among constant-degree algebraic arcs. Our results almost completely settle a 35-year-old open problem in computational geometry motivated by hidden-surface removal in computer graphics. We also discuss several algorithms for constructing a small set of cuts so as to eliminate all depth-relation cycles among the lines.

    Original languageEnglish (US)
    Pages (from-to)725-741
    Number of pages17
    JournalDiscrete and Computational Geometry
    Volume59
    Issue number3
    DOIs
    StatePublished - Apr 1 2018

    Keywords

    • Algebraic methods in combinatorial geometry
    • Cycle elimination
    • Depth cycles
    • Depth order
    • Painter’s algorithm
    • Polynomial partition

    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 'Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions'. Together they form a unique fingerprint.

  • Cite this