2016/07/20 by Boris Aronov, Aronov, Boris, Edward Y. Miller +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1607.06136
28 pages, 4 figures
openalex publication_date 2016/07/20 · arxiv created 2019/03/07 · arxiv updated 2019/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given n pairwise openly disjoint triangles in 3-space, their vertical depth relation may contain cycles. We show that, for any ε>0, the triangles can be cut into O(n3/2+ε) connected semi-algebraic pieces, whose description complexity depends only on the choice of ε, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem, in this full generality, with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors (Aronov, Sharir~2018) on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.