Russ Miller

Dept. of Computer Science, State University of New York at Buffalo

Quentin F. Stout

Computer Science and Engineering, University of Michigan

**Abstract:**
We present optimal
parallel algorithms for using a mesh-connected parallel computer to determine
several fundamental geometric
properties of planar objects.
For example, given multiple sets represented by the Cartesian coordinates
of *n* or fewer planar vertices,
distributed one point per processor on a square
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.

Since any mesh computer must take
Ω(√n) time on the above problems given the specified input format,
all of these algorithms are optimal.
While not discussed in the paper, many of these algorithms can easily
be extended to
solve the same problems in Θ(n^{1/d}) time on a d-dimensional
mesh-connected computer, where the implied constants depend upon d.

**Keywords:** parallel algorithm, mesh computer, mesh-connected
computer, array processor, computational geometry,
planar point data, convexity, proximity, area, intersection

**Complete paper.**
This appears in *IEEE Transactions on Computers* C-38 (1989),
pp. 321-340.
IEEE digitized it and made it available.
A preliminary version of some of these algorithms appeared in
Miller, R and Stout, QF,
"Computational geometry on a mesh-connected computer",
Proc. 1984 International Conf. Parallel Processing (ICPP), 66-73.

- Most of the contents of this paper have been incorporated into the book R Miller and QF Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids, MIT Press, 1996
- My papers in parallel computing
- Overview of my research in parallel computing

Copyright © 2005-2018 Quentin F. Stout |