TY - GEN

T1 - Randomized parallel algorithms for trapezoidal diagrams

AU - Clarkson, Kenneth L.

AU - Cole, Richard

AU - Tarjan, Robert E.

N1 - Funding Information:
*Work was supported in part by NSF grants CCR-8902221 and CCR-8906949. t Research at Princeton University partially supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant NSF-STC88-09648 and by the Na-tionaf Science Foundation, Grant No. CCR-8920505.
Publisher Copyright:
© 1991 ACM.

PY - 1991/6/1

Y1 - 1991/6/1

N2 - We describe randomized parallel CREW PRAM algorithms for building trapezoidal diagrams of line segments in the plane. For general segments, we give an algorithm requiring optimal O(A + nlogn) expected work and optimal O(logn) time, where A is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal O(n) expected work and O(log n log log ra log∗ n) expected time, and a simpler algorithm requiring O(n log∗ n) expected work. The serial algorithm corresponding to the latter is the simplest known algorithm requiring O(n log∗ n) expected operations. For a set of segments forming K chains, we give an algorithm requiring O(A + n log∗ n + K log n) expected work and O(log n log log n log∗ n) expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every log n steps.

AB - We describe randomized parallel CREW PRAM algorithms for building trapezoidal diagrams of line segments in the plane. For general segments, we give an algorithm requiring optimal O(A + nlogn) expected work and optimal O(logn) time, where A is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal O(n) expected work and O(log n log log ra log∗ n) expected time, and a simpler algorithm requiring O(n log∗ n) expected work. The serial algorithm corresponding to the latter is the simplest known algorithm requiring O(n log∗ n) expected operations. For a set of segments forming K chains, we give an algorithm requiring O(A + n log∗ n + K log n) expected work and O(log n log log n log∗ n) expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every log n steps.

UR - http://www.scopus.com/inward/record.url?scp=77951880810&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951880810&partnerID=8YFLogxK

U2 - 10.1145/109648.109665

DO - 10.1145/109648.109665

M3 - Conference contribution

AN - SCOPUS:77951880810

SN - 0897914260

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 152

EP - 161

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Association for Computing Machinery

T2 - 7th Annual Symposium on Computational Geometry, SCG 1991

Y2 - 10 June 1991 through 12 June 1991

ER -