Randomized Parallel Algorithms for Trapezoidal Diagrams
Abstract:
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.