Computational Geometry on a Systolic Chip

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

This paper describes systolic algorithms for a number of geometric problems. For the sake of realism we restrict our investigation to one-dimensional arrays whose communication links with the outside are located at the end cells. Implementations yielding maximal throughput are given for solving dynamic versions of convex hull, inclusion, range and intersection search, planar point location, intersection, triangulation, and closest-point problems.

Original languageEnglish (US)
Pages (from-to)774-785
Number of pages12
JournalIEEE Transactions on Computers
VolumeC-33
Issue number9
DOIs
StatePublished - Sep 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Analysis of algorithms
  • VLSI
  • computational geometry
  • convolution
  • parallel computation
  • pipelining real-time algorithms
  • systolic arrays

Fingerprint

Dive into the research topics of 'Computational Geometry on a Systolic Chip'. Together they form a unique fingerprint.

Cite this