RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
- 1 June 1992
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 02 (02) , 117-133
- https://doi.org/10.1142/s0218195992000081
Abstract
We describe randomized parallel algorithms for building trapezoidal diagrams of line segments in the plane. The algorithms are designed for a CRCW PRAM. 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 among the simplest known algorithms 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.Keywords
This publication has 0 references indexed in Scilit: