TY - GEN
T1 - Optimal parallel algorithms for polygon and point-set problems (Preliminary Version)
AU - Cole, Richard
AU - Goodrich, Michael T.
N1 - Funding Information:
We present a number of new algorithms for parallel computational geometry \[1,2,3,4,7,9,10\]. Our goal is to find algorithms that run as fast as possible and are efficient in the following sense: if P(n) is the processor complexity, T{n) the parallel time complexity, and Seq(n) the time complexity of the best known sequential algorithm for the problem under consideration, then T(n} * P(n) = O(Seq(n)). If the product T(n) * P(n) achieves the sequential lower bound for the problem, then we say the algorithm is optimal. All of our algorithms are optimal in this sense and are for the EREW or CREW PRAM models. The weaker of these two is the EREW PRAM model, the synchronous shared memory model in which simultaneous reads or writes are not allowed. In the CREW PRAM we allow for simultaneous reads. Specifically, our results are the following: 1This research was supported in part by NSF grants DCR-84-01633 and CCR-8702271, and by ONR grant N00014-85-K-0046. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copyingi s by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and / or specificp ermission.
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 -