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)