Removing depth-order cycles among triangles:an algorithm generating triangular fragments

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 R3 into a subquadratic number of fragments such that the resulting fragments admit a depth order? They managed to prove an O(n9 / 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(n3/2polylogn) fragments suffice for any set of lines. In a follow-up paper Aronov et al. proved an O(n3/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 R3 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 R3 into O(n7/4polylogn) triangular fragments that admit a depth order. The running time of our algorithm is O(n3.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(n1+ε+n1/4K3/4polylogn) fragments suffice to obtain a depth order. This result extends to xy-monotone surface patches bounded by a constant number of bounded-degree algebraic arcs in general position, constituting the first subquadratic bound for surface patches.