AN EFFICIENT VLSI ARCHITECTURE WITH APPLICATIONS TO GEOMETRIC PROBLEMS Academic Article uri icon

abstract

  • We present a parallel organization with a reduced number of processors and special communication features for efficient solutions to problems in computational geometry. The organization has n processors operating in synchronous mode with row and column access to an n n array of memory modules. The organization has simple regular structure and can be implemented in VLSI on a single chip or using a limited chip set. We develop fast parallel algorithms for computing several geometric properties of a set of n2 points in the plane. We present O(n log n) time parallel algorithms to compute the convex hull of n2 points in the plane, to compute the intersection of two convex polygons each having n2 edges, and to compute the diameter and a smallest enclosing box of a set of n2 points. All these problems require O(n2 log n) sequential time. Thus, all our solutions are optimal in the sense that their processor-time product is equal to the sequential complexity of these problems. We also consider the problem of computing nearest neighbors when the n2 points belong to an n n digitized image. We show that this problem can be solved on the proposed parallel organization in O(n) time using n PEs, which is the same time taken by a two-dimensional mesh-connected computer with n2 processors to solve the same problem. 1989.

published proceedings

  • PARALLEL COMPUTING

altmetric score

  • 3

author list (cited authors)

  • ALNUWEIRI, H. M., & KUMAR, V.

citation count

  • 4

complete list of authors

  • ALNUWEIRI, HM||KUMAR, VKP

publication date

  • October 1989