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 -