Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions

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.