On computing the upper envelope of segments in parallel
Wei Chen, K. Wada · 2002
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,+/spl infin/). We give efficient parallel methods for finding the upper envelope of k-intersecting segments for any integer k/spl ges/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/sup 1+/spl epsiv//n) time using 0(/spl lambda//sub k+1/(n)/log/sup /spl epsiv//n) processors for any /spl epsiv/>0, where /spl lambda//sub k+2/(n)/sup 1/ 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).