Removing Depth-Order Cycles Among Triangles: An Algorithm Generating Triangular Fragments
Mark de Berg · Discrete & Computational Geometry · 2019
Abstract More than 25 years ago, inspired by applications in computer graphics, Chazelle et al. studied the following question: is it possible to cut any set of n lines or other objects in $${\mathbb R}^3$$ R 3 into a subquadratic number of fragments such that the resulting fragments admit a depth order? They managed to prove an $$O(n^{9/5})$$ O ( n 9 / 5 ) bound on the number of fragments, but only for the very special case of bipartite weavings of lines. Since then only little progress was made, until a breakthrough in 2016 by Aronov and Sharir, who showed that $$O(n^{3/2}{{\,\mathrm{polylog}\,}}n)$$ O ( n 3 / 2 polylog n ) fragments suffice for any set of lines. In a follow-up paper Aronov et al. proved an $$O(n^{3/2+\varepsilon })$$ O ( n 3 / 2 + ε ) bound for triangles, but their method uses high- (albeit constant-) degree algebraic arcs to perform the cuts. Hence, the resulting pieces have curved boundaries. Thus the following natural version of the problem is still wide open: is it possible to cut any collection of n disjoint triangles in $${\mathbb R}^3$$ R 3 into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of n disjoint triangles in $${\mathbb R}^3$$ R 3 into $$O(n^{7/4}{{\,\mathrm{polylog}\,}}n)$$ O ( n 7 / 4 polylog n ) triangular fragments that admit a depth order. The running time of our algorithm is $$O(n^{3.69})$$ O ( n 3.69 ) . We also prove a refined bound that depends on the number, K , of intersections between the projections of the triangle edges onto the xy -plane: we show that $$O(n^{1+\varepsilon } + n^{1/4} K^{3/4}{{\,\mathrm{polylog}\,}}n)$$ O ( n 1 + ε + n