Crossing distribution (circuit layout CAD)
D.C. Wang, C.B. Shung · Proceedings EURO-DAC '92: European Design Automation Conference · 2003
The problem of distributing the set of crossings between two regions is studied. A crossing is defined as the intersection of two nets. Three types of crossing-distribution problems are considered: (1) the quota problem, (2) the membership problem, and (3) the combination problem, which is a combination of the quota and membership problems. The objective is to find a net ordering at the boundary between two regions such that the quota and membership problems are resolved, and the total number of crossings is minimized. The authors propose the use of computational geometry techniques for the solution of the quota problem in O(n log n) time, the use of a depth-first search to solve the membership in O(n/sup 2/) time, and the use of a breadth-first search to solve the combination problem in O(n/sup 2/) time, where n is the number of tests.>