Upper envelope onion peeling

AbstractWe consider the problem of finding the upper envelope layers of a set of line segments, sequentially and in parallel. The upper envelope of a set of n line segments in the plane can be computed in O(n log n) time (Hershberger, 1989). By repeatedly removing the segments that appear on the envelope and recomputing the envelope, one obtains a natural partition of the set of segments into layers. We given an O(n log n) sequential algorithm to find envelope layers if the segments are disjoint and an O(nα(n)log2 n) algorithm if the segments intersect (α(n) is the extremely slowly-growing inverse of Ackermann's function (Hart and Sharir, 1986)). Finally, we prove that the problem of finding envelope layers is P-complete, and hence likely to be intractable in parallel. The envelope layers problem is one of the first two computational geometry problems to be proved P-complete