TY - GEN

T1 - Optimal parallel algorithms for polygon and point-set problems (Preliminary Version)

AU - Cole, Richard

AU - Goodrich, Michael T.

N1 - Publisher Copyright:
© 1988 ACM.

PY - 1988/1/6

Y1 - 1988/1/6

N2 - In this paper we give parallel algorithms for a number of problems defined on polygons and point sets. All of our algorithms have optimal T(n) ∗ P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. In addition, our algorithms provide parallel analogues to well known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently that point-set problems, and that one can solve nearest-neighbor problems without explicitly constructing a Voronoi diagram.

AB - In this paper we give parallel algorithms for a number of problems defined on polygons and point sets. All of our algorithms have optimal T(n) ∗ P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. In addition, our algorithms provide parallel analogues to well known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently that point-set problems, and that one can solve nearest-neighbor problems without explicitly constructing a Voronoi diagram.

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

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

U2 - 10.1145/73393.73414

DO - 10.1145/73393.73414

M3 - Conference contribution

AN - SCOPUS:85030065655

T3 - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

SP - 201

EP - 210

BT - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

PB - Association for Computing Machinery, Inc

T2 - 4th Annual Symposium on Computational Geometry, SCG 1988

Y2 - 6 June 1988 through 8 June 1988

ER -