DocumentCode
886122
Title
The number of intersections between two rectangular paths
Author
Wang, Yue-Li ; Lee, R.C.T. ; Chang, J.S.
Author_Institution
Nat. Tsing Hua Univ., Hsinchu, Taiwan
Volume
38
Issue
11
fYear
1989
fDate
11/1/1989 12:00:00 AM
Firstpage
1564
Lastpage
1571
Abstract
The authors consider upper bounds on the number of intersections between two rectangular paths. Let these two paths be denoted as P and Q , and denote the number of Manhattan subpaths in P and Q by |P | and |Q | respectively. K. Kant (1985) gave an upper bound of 10|P ||Q |/9+4(| P |+|Q |)/9. The authors have sharpened these upper bounds, using methods to break the rectangular paths into subpaths, to be |P ||Q |+[|P |/2]+[|Q |/3], where they assume without loss of generality that |P |⩽|Q |
Keywords
circuit layout; computational complexity; graph theory; Manhattan subpaths; Councils; Heuristic algorithms; Interference; Printed circuits; Quadratic programming; Routing; Shape; Upper bound; Very large scale integration; Wires;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.42126
Filename
42126
Link To Document