Quick links

Randomized Parallel Algorithms for Trapezoidal Diagrams

Report ID:
TR-318-91
Date:
March 1991
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.
  • Follow us: Facebook Twitter Linkedin