1992/06/01 by Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Combinatorial Mathematics #Data Management and Algorithms #Binary logarithm #Log-log plot #Mathematics #Combinatorics #Randomized algorithm #Algorithm #Parallel algorithm #Deterministic algorithm #Set (abstract data type) #Time complexity #Efficient algorithm #Discrete mathematics #Computer science
paper · doi:10.1142/s0218195992000081
openalex publication_date 1992/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.