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 thenearest neighbors of a set of planar points represented by their Cartesian coordinates. The algorithm executes on a√n×√n MCC, and requires an optimalO(√n) time. An algorithm for constructing theconvex hull of a set of planar points and anupdate algorithm for thedisk placement problem on ann 2/3×n 2/3 two-dimensional systolic array are presented. Both these algorithms requireO(n 2/3) time steps. The advantage of the systolic solutions lies in their suitability for direct hardware implementation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. L. Bentley and M. I. Shamos, Divide- and-conquer in multidimensional space, inProc. of 8th Ann. ACM Symp. on Theory of Computing, 1976, pp. 220–230.
B. M. Chazelle, Computational geometry on a systolic chip,IEEE Trans. Comput.,33 (1984), 774–785.
B. M. Chazelle, Intersecting is easier than sorting, inProc. of 16th ACM Symp. on Theory of Computing, 1984, pp. 125–134.
B. M. Chazelle and D. T. Lee, On a circle placement problem, inProc. of Conf. on Information Systems Science, 1984.
F. Dehne,O(n 1/2) algorithms for maximal elements and ECDF searching problem on a mesh-connected parallel computer,Inform. Process. Lett.,22 (1986), 303–306.
R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set,Inform. Process. Lett.,1 (1972), 132–133.
H. T. Kung, Why systolic architectures?,Computer,15 (1982), 37–46.
M. Lu, Constructing the Voronoi diagram on a mesh-connected computer, inProc. of 1986 Int. Conf. on Parallel Processing, 1986, pp. 806–811.
M. Lu and P. Varman, Solving geometric proximity problems on mesh-connected computers, inProc. of 1985 IEEE Comp. Soc. Workshop on Computer Architecture for Pattern Analysis and Image Database Management, 1985, pp. 248–255.
M. Lu and P. Varman, Mesh-connected computer algorithms for rectangle-intersection problems, inProc. of 1986 Int. Conf. on Parallel Processing, 1986, pp. 301–307.
R. Miller and Q. F. Stout, Computational geometry on a mesh-connected computer, inProc. of 1984 Int. Conf. on Parallel Processing, 1984, pp. 66–73.
R. Miller and Q. F. Stout, Mesh Computer Algorithms for Computational Geometry, Technical Report 86-18, Department of Computer Science, State University of New York at Buffalo, July 1986.
D. Nassimi and S. Sahni, Data broadcasting in SIMD computers,IEEE Trans. Comput.,30 (1981), 101–106.
F. P. Preparata and D. T. Lee, Computational geometry—a survey,IEEE Trans. Comput.,33 (1984), 1072–1100.
C. D. Thompson and H. T. Kung, Sorting on a mesh-connected parallel computer,Comm. ACM,20 (1977), 263–271.
Author information
Authors and Affiliations
Additional information
This research was partially supported by an IBM Faculty Development Award.
Rights and permissions
About this article
Cite this article
Lu, M., Varman, P. Geometric problems on two-dimensional array processors. Circuits Systems and Signal Process 7, 191–211 (1988). https://doi.org/10.1007/BF01602097
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01602097