Vertical decompositions for triangles in 3-space
Marc de Berg, Leonidas Guibas, Dan Halperin · 1994
We prove that, for any constant ε>0, the complexity of the vertical decomposition of a set of n triangles in three-dimensional space is O(n2+ε+K), where K is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to be O(n2+ε). These bounds are almost tight in the worst case.