Randomized Parallel Algorithms for Trapezoidal Diagrams

Report ID: TR-318-91

---

Author: Clarkson, Kenneth L. / Tarjan, Robert E. / Cole, Richard

---

Date: 1991-04-00

---

Pages: 11

---

Download Formats: |PDF|

---

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.