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 Θ(n1/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.
|
Copyright © 2005-2018 Quentin F. Stout |