Abstract: We present optimal parallel algorithms for using a mesh-connected parallel computer to determine several fundamental geometric properties of objects. For example, given multiple sets represented by the Cartesian coordinates of n or fewer planar vertices, distributed one point per processor on a 2-dimensional mesh-connected computer with n processors, we give Θ(√n) algorithms for identifying the convex hull and smallest enclosing box of each set. Given two such sets, we give a Θ(√n) algorithm to decide if the sets are linearly separable. Given n or fewer planar points, one per processor, we give Θ(√n) time algorithms to solve the all-nearest neighbor problem for points and for sets of labeled points. Given n or fewer circles, convex polygons, hyperplanes, simple polygons, orthogonal polygons, or iso-oriented rectangles, one per processor, we give Θ(√n) time algorithms to solve a variety of area and intersection problems.

Keywords: parallel algorithm, mesh computer, mesh-connected computer, computational geometry, planar point data, convexity, proximity, area, intersection, parallel computer, discrete mathematics, computer science.

Complete paper. This paper appears in IEEE Transactions on Computers C-38 (1989), pp. 321-340. IEEE digitized it and made it available.

• Most of the contents of this paper have been incorporated into the book   Parallel Algorithms for Regular Architectures: Meshes and Pyramids
• My papers in parallel computing
• Overview of my research in parallel computing

Copyright © 2005-2008 Quentin F. Stout