Optimal parallel algorithms for polygon and point-set problems
Richard Cole, Michael T. Goodrich · 1988
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.