Cutting triangular cycles of lines in space

摘要

We show that a collection of lines in 3-space can be cut into a subquadratic number of 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.