On computing the upper envelope of segments in parallel

Given a collection of segments in the plane that intersect pairwise at most k times, regarding the segments as opaque barriers, their upper envelope consists of the portions of the segments visible from point (0,+∞). We give efficient parallel methods for finding the upper envelope of k-intersecting segments for any integer k⩾0, in the weakest shared memory model, the EREW PRAM. We show that the upper envelope of n k-intersecting segments can be found in 0(log^1+εn) time using 0(λ_k+1(n)/log ^εn) processors for any ε>0, where λ_k+2(n)¹ is the size of the upper envelope. In particular, for line segments we show the following optimal algorithms: the upper envelope of n line segments can be found in O(log n) time using O(n) processors, and if the line segments are nonintersecting and sorted, the envelope can be found in O(log n) time using O(n/log n) processors. We also show that our methods imply a fast sequential result: the upper envelope of n sorted line segments can be found in O(n log log n) time sequentially, which improves the known lowest upper bound O(n log n)