Parallel computational geometry (Q1115600)

This paper contributes efficient parallel algorithms for solving some basic geometric problems. ``Efficient'' here means polylogarithmic in parallel time. All the algorithmus presented are algorithms executable in polylog depth on polynomial-size circuits. Such algorithms usually are called NC-algorithms. Many of the problems considered in this paper are known to have \(\Omega\) (n log n) lower bounds in the algebraic computation tree model. Standard techniques in the subject such as contour-tracing, plane-sweeping and gift-wrapping initially seem inherently sequential. One of the main contributions of the paper is to show that NC-analogues of these techniques actually exist. Some of the problems of planar convex hulls, planar Voronoi-diagrams and three-dimensional convex hulls (with the same \(\Theta\) (n log n) sequential time complexity) are shown to be in \(NC^+_ 1(n)\), \(NC^+_ 2(n)\), \(NC^+_ 3(n)\), respectively. The notation \(NC^+_ k(f(u))\) indicates the class of algorithms running on a PRAM (P for parallel) using f(u) processors and halting in \(O(\log^ k(n))\) steps. Further problems discussed in this paper are other proximity problems, segment intersections, triangulations of polygons, polygon optimization problems and creating data structures in two and three dimensions to answer standard queries.