Geometric problems on two-dimensional array processors
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Parallel algorithms for solving geometric problems on two array processor models-the mesh-connected computer (MCC) and a two-dimensional systolic array-are presented. We illustrate a recursive divide- and-conquer paradigm for MCC algorithms by presenting a time-optimal solution for the problem of finding the nearest neighbors of a set of planar points represented by their Cartesian coordinates. The algorithm executes on a nn MCC, and requires an optimal O(n) time. An algorithm for constructing the convex hull of a set of planar points and an update algorithm for the disk placement problem on an n2/3n2/3 two-dimensional systolic array are presented. Both these algorithms require O(n2/3) time steps. The advantage of the systolic solutions lies in their suitability for direct hardware implementation. 1988 Birkhuser Boston Inc.
