Computational Geometry on a Systolic Chip

Research output: Contribution to journalArticlepeer-review

50 Scopus citations


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
Issue number9
StatePublished - Sep 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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


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

Cite this