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
fDate :
11/1/1989 12:00:00 AM
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;
Journal_Title :
Computers, IEEE Transactions on
