Randomized parallel algorithms for trapezoidal diagrams

Kenneth L. Clarkson, Richard Cole, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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 + nlogn) expected work and optimal O(logn) 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 ra 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.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual Symposium on Computational Geometry
PublisherAssociation for Computing Machinery
Pages152-161
Number of pages10
ISBN (Print)0897914260
DOIs
StatePublished - Jun 1 1991
Event7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States
Duration: Jun 10 1991Jun 12 1991

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other7th Annual Symposium on Computational Geometry, SCG 1991
CountryUnited States
CityNorth Conway
Period6/10/916/12/91

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Randomized parallel algorithms for trapezoidal diagrams'. Together they form a unique fingerprint.

  • Cite this

    Clarkson, K. L., Cole, R., & Tarjan, R. E. (1991). Randomized parallel algorithms for trapezoidal diagrams. In Proceedings of the Annual Symposium on Computational Geometry (pp. 152-161). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/109648.109665