Mesh computer algorithms for computational geometry

Asymptotically optimal parallel algorithms are presented for use on 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, Θ(n^1/2 ⩾-time algorithms are given for identifying the convex hull and smallest enclosing box of each figure. Given two such figures, a Θ(n^1/2⩾-time algorithm is given to decide if the two figures are linearly separable. Given n or fewer planar points, Θ(n^1/2⩾-time algorithms are given to solve the all-nearest neighbor problems for points and for sets of points. Given n or fewer circles, convex figures, hyperplanes, simple polygons, orthogonal polygons, or iso-oriented rectangles, Θ(n^1/2⩾-time algorithms are given to solve a variety of area and intersection problems. Since any serial computer has worst-case time of Ω(n) when processing n points, these algorithms show that the mesh computer provides significantly better solutions to these problems