TY - JOUR
T1 - A polynomial time algorithm for optimal routing around a rectangle
AU - Lapaugh, Andrea S.
N1 - Funding Information:
* This research was supported in part by NSF Grant MCS 78..;05849 and by a Xerox Spccial Opportunity reUowship.
Publisher Copyright:
© 1980 IEEE Computer Society. All rights reserved.
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 -