In IEEE Transactions on Computers C-38 (1989), pp. 321-340.

Mesh Computer Algorithms for Computational Geometry

Russ Miller
Dept of Comp Sci & Eng, State University of New York at Buffalo

Quentin F. Stout
EECS Department, University of Michigan

Abstract: 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 2-dimensional mesh computer with n simple processing elements, we give Theta(sqrt(n)) algorithms for identifying the convex hull and smallest enclosing box of each figure. Given two such figures, we give a Theta(sqrt(n)) algorithm to decide if the two figures are linearly separable. Given n or fewer planar points, we give Theta(sqrt(n)) 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 Theta(sqrt(n)) time algorithms to solve a variety of area and intersection problems. Since any serial computer has worst-case time of Omega(n) when processing n points, our algorithms show that the mesh computer provides significantly better solutions to these problems.

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

IEEE has digitized this paper and made it available.
Full paper (PDF) Full paper (compressed Postscript)
Full paper (Postscript)


Much of the content of this paper has been incorporated into the book Parallel Algorithms for Regular Architectures: Meshes and Pyramids, by R. Miller and Q.F. Stout. More information about the book is available.

Russ Miller (miller@cse.buffalo.edu)