A polynomial time algorithm for optimal routing around a rectangle

Andrea S. Lapaugh

doi:10.1109/SFCS.1980.4567829

A polynomial time algorithm for optimal routing around a rectangle

Andrea S. Lapaugh

Computer Science

Research output: Contribution to journal › Conference article › peer-review

4 Scopus citations

Abstract

In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of line segments orthogonal to the sides of the component Paths may intersect at a point but may not overlap. The criterion for optimality is the area of a rectangle with sides orthogonal to those of the component which circumscribes the component and paths. The algorithm has running time O(t³), where t is the number of terminals on the component.

Original language	English (US)
Article number	4567829
Pages (from-to)	282-293
Number of pages	12
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1980.4567829
State	Published - 1980
Event	21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States Duration: Oct 13 1980 → Oct 15 1980

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/SFCS.1980.4567829

Cite this

@article{7c439dbedf8c45d3aeb8bbebdce2ddd0,

title = "A polynomial time algorithm for optimal routing around a rectangle",

abstract = "In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of line segments orthogonal to the sides of the component Paths may intersect at a point but may not overlap. The criterion for optimality is the area of a rectangle with sides orthogonal to those of the component which circumscribes the component and paths. The algorithm has running time O(t3), where t is the number of terminals on the component.",

author = "Lapaugh, {Andrea S.}",

note = "Publisher Copyright: {\textcopyright} 1980 IEEE Computer Society. All rights reserved.; 21st Annual Symposium on Foundations of Computer Science, FOCS 1980 ; Conference date: 13-10-1980 Through 15-10-1980",

year = "1980",

doi = "10.1109/SFCS.1980.4567829",

language = "English (US)",

pages = "282--293",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - A polynomial time algorithm for optimal routing around a rectangle

AU - Lapaugh, Andrea S.

PY - 1980

Y1 - 1980

N2 - In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of line segments orthogonal to the sides of the component Paths may intersect at a point but may not overlap. The criterion for optimality is the area of a rectangle with sides orthogonal to those of the component which circumscribes the component and paths. The algorithm has running time O(t3), where t is the number of terminals on the component.

AB - In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of line segments orthogonal to the sides of the component Paths may intersect at a point but may not overlap. The criterion for optimality is the area of a rectangle with sides orthogonal to those of the component which circumscribes the component and paths. The algorithm has running time O(t3), where t is the number of terminals on the component.

UR - http://www.scopus.com/inward/record.url?scp=85040214482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040214482&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1980.4567829

DO - 10.1109/SFCS.1980.4567829

M3 - Conference article

AN - SCOPUS:85040214482

SN - 0272-5428

SP - 282

EP - 293

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567829

T2 - 21st Annual Symposium on Foundations of Computer Science, FOCS 1980

Y2 - 13 October 1980 through 15 October 1980

ER -

A polynomial time algorithm for optimal routing around a rectangle

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this