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^+^n$ log $n)$ expected work and optimal $O$(log $n)$ 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 $n$ 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.

This technical report has been published as

Randomized Parallel Algorithms for Trapezoidal Diagrams.
Kenneth L. Clarkson, Richard Cole and Robert E. Tarjan,

Seventh Annual Symp. on Computational Geometry (1991) 152-161 and

Internat. J. of Computational Geometry Applications 2 (1992) 117-133.