Mesh Computer Algorithms for Computational Geometry

We present asymptotically optimal parallel algorithms for using a mesh computer to determine several fundamental geometric properties of figures. For example, given multiple figures represented by the Cartesian coordinates of n or fewer planar vertices, distributed one point per processor on a two-dimensional mesh computer with n simple processing elements, we give θ(n1/2) time algorithms for identifying the convex hull and smallest enclosing box of every figure. Given two such figures, we give a θ(n1/2) time algorithm to decide if the two figures are linearly separable. Given n or fewer planar points, we give θ(n1/2) time algorithms to solve the all-nearest neighbor problem for points and for sets of points. Given n or fewer circles, convex figures, hyperplanes, simple polygons, orthogonal polygons, or iso-oriented rectangles, we give θ(n1/2) time algorithms to solve a variety of area and intersection problems. Since any serial computer has worst case time of Ω(n) when processing n points, our algorithms show that the mesh computer provides significantly better solutions to these problems.