Geometric problems on two-dimensional array processors Academic Article uri icon


  • 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.

published proceedings

  • Circuits, Systems, and Signal Processing

author list (cited authors)

  • Lu, M. i., & Varman, P.

citation count

  • 2

complete list of authors

  • Lu, Mi||Varman, Peter

publication date

  • June 1988