Efficient parallel techniques for computational geometry
Michael T. Goodrich, Mikhail J. Atallah · Purdue e-Pubs (Purdue University System) · 1987
In this thesis we present a number of new techniques for solving many of the fundamental problems in computational geometry efficiently in parallel. The resulting algorithms all have linear or "almost" linear speed-ups over the best known sequential algorithms for these problems. Specifically, the problems we address include the following: computing the diameter of a convex polygon, planar convex hull finding, finding a closest pair of points, polygon triangulation, 3-dimensional maxima finding, dominance counting, determining the visibility from a point, trapezoidal decomposition, and planar point location. The techniques presented are quite different from the ones used in the efficient sequential algorithms. All of our results are for the CREW PRAM or EREW PRAM computational models.