An efficient VLSI architecture with applications to geometric problems

Hussein M. Alnuweiri*, V. K. Prasanna Kumar

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)71-93
Number of pages23
JournalParallel Computing
Volume12
Issue number1
DOIs
Publication statusPublished - Oct 1989
Externally publishedYes

Keywords

  • Parallel algorithms
  • VLSI architecture
  • computational geometry
  • processor-time optimal solutions

Fingerprint

Dive into the research topics of 'An efficient VLSI architecture with applications to geometric problems'. Together they form a unique fingerprint.

Cite this