Some geometry for general river routing

Alan Siegel, Danny Dolev

Research output: Contribution to journalArticle

Abstract

Efficient solutions are given to compute the optimal placement for a pair of VLSI modules interconnected by river routing. Specifically, let the (perpendicular) distance between the two modules be the separation, and call the (transverse) displacement the offset. This paper principally considers the separation problem: Given an offset and a wiring rule, find the minimum separation permitting a legal wiring. The design rules might use wires which are exclusively rectilinear, polygonal with a finite number of slopes, or possibly restricted to some other class of shapes such as circular arcs plus linear pieces. Techniques are developed which unify a variety of different placement problems, and give efficient solutions under extremely general conditions.

Original languageEnglish (US)
Pages (from-to)583-605
Number of pages23
JournalSIAM Journal on Computing
Volume17
Issue number3
DOIs
StatePublished - 1988

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Some geometry for general river routing'. Together they form a unique fingerprint.

  • Cite this