Computing and Verifying Depth Orders
Mark de Berg, Mark Overmars, Otfried Cheong Schwarzkopf · SIAM Journal on Computing · 1994
A depth order on a set of line segments in 3-space is an order such that line segment a comes before line segment $a'$ in the order when a lies below $a'$ or, in other words, when there is a vertical ray that first intersects $a'$ and then intersects a. Efficient algorithms for the computation and verification of depth orders of sets of n line segments in 3-space are presented. The algorithms run in time $O(n^{{4 / 3} + \varepsilon } )$, for any fixed $\varepsilon > 0$. If all line segments are axis-parallel or, more generally, have only a constant number of different orientations, then the sorting algorithm runs in $O(n\log ^3 n)$, for any fixed $\varepsilon > 0$ time and the verification takes $O(n\log ^2 n)$ time. The algorithms can be generalized to handle triangles and other polygons instead of line segments. They are based on a general framework for computing and verifying linear orders extending implicitly defined binary relations.