Randomized parallel algorithms for trapezoidal diagrams

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

doi:10.1145/109648.109665

Randomized parallel algorithms for trapezoidal diagrams

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English (US)
Title of host publication	Proceedings of the Annual Symposium on Computational Geometry
Publisher	Association for Computing Machinery
Pages	152-161
Number of pages	10
ISBN (Print)	0897914260
DOIs	https://doi.org/10.1145/109648.109665
State	Published - Jun 1 1991
Event	7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States Duration: Jun 10 1991 → Jun 12 1991

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	7th Annual Symposium on Computational Geometry, SCG 1991
Country/Territory	United States
City	North Conway
Period	6/10/91 → 6/12/91

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/109648.109665

Cite this

Randomized parallel algorithms for trapezoidal diagrams. / Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E.
Proceedings of the Annual Symposium on Computational Geometry. Association for Computing Machinery, 1991. p. 152-161 (Proceedings of the Annual Symposium on Computational Geometry).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Clarkson, KL, Cole, R & Tarjan, RE 1991, Randomized parallel algorithms for trapezoidal diagrams. in Proceedings of the Annual Symposium on Computational Geometry. Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, pp. 152-161, 7th Annual Symposium on Computational Geometry, SCG 1991, North Conway, United States, 6/10/91. https://doi.org/10.1145/109648.109665

@inproceedings{0b462d7dd12445eaa64642c2c3e7d4f8,

title = "Randomized parallel algorithms for trapezoidal diagrams",

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.",

author = "Clarkson, {Kenneth L.} and Richard Cole and Tarjan, {Robert E.}",

note = "Publisher Copyright: {\textcopyright} 1991 ACM.; 7th Annual Symposium on Computational Geometry, SCG 1991 ; Conference date: 10-06-1991 Through 12-06-1991",

year = "1991",

month = jun,

day = "1",

doi = "10.1145/109648.109665",

language = "English (US)",

isbn = "0897914260",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery",

pages = "152--161",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

}

TY - GEN

T1 - Randomized parallel algorithms for trapezoidal diagrams

AU - Clarkson, Kenneth L.

AU - Cole, Richard

AU - Tarjan, Robert E.

PY - 1991/6/1

Y1 - 1991/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77951880810&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951880810&partnerID=8YFLogxK

U2 - 10.1145/109648.109665

DO - 10.1145/109648.109665

M3 - Conference contribution

AN - SCOPUS:77951880810

SN - 0897914260

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 152

EP - 161

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Association for Computing Machinery

T2 - 7th Annual Symposium on Computational Geometry, SCG 1991

Y2 - 10 June 1991 through 12 June 1991

ER -

Randomized parallel algorithms for trapezoidal diagrams

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this