Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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 andInternat. J. of Computational Geometry Applications2(1992) 117-133.