Abstract
In this paper an O(N log N) algorithm for routing through a rectangle is presented. Consider an n-by-m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in O(N log N) time; this contrasts favorably with the area of the layout that might be as large as N2. The layout constructed can be wired using four layers of interconnect with only O(N) contact cuts. A partial extension to multiterminal nets is also discussed.
- 1 BENTLEY, J. L. Solution to Klee's rectangle problems. Unpublished notes. Carnegie-Mellon University, Pittsburgh, Pa., 1977.Google Scholar
- 2 BRADY, M., AND BROWN, D.J. VLSI routing: Four layers suffice. Adv. Comput. Res. 2: VLS! Theory (1984), 245-257.Google Scholar
- 3 FRANK, A. Disjoint paths in a rectilinear grid. Combinatorica 2, 4 (I982), 361-37 i.Google Scholar
- 4 LIPSKI, W., JR., AND PREPARATA, F.P. Finding the contour of a union ofiso-oriented rectangles. J. Alg. 1 (1980), 235-246.Google Scholar
- 5 MCCREIGHT, E. M. Priority search trees. Res. Rep. CSL-81-5. Xerox Corporation, Palo Alto, Calif., January 1982.Google Scholar
- 6 PREPARATA, F. P., AND LIPSKI, W., JR. Optimal three-layer channel routing. IEEE Trans. Comput. 33, 5 (May 1984), 427-437. Google Scholar
- 7 RiVEST, R. L., BARATZ, A. E., AND MILLER, G. Provably good channel routing algorithms. In Proceedings of the CMU Conference on VLSI Systems and Computations (Pittsburgh, Oct. 19-21). Computer Science Press, Rockville, Md., 198 l, pp. 15 l- 159.Google Scholar
Index Terms
- Routing through a rectangle
Recommendations
Fast algorithms for computing the largest empty rectangle
SCG '87: Proceedings of the third annual symposium on Computational geometryWe provide two algorithms for solving the following problem: Given a rectangle containing n points, compute the largest-area and the largest-perimeter subrectangles with sides parallel to the given rectangle that lie within this rectangle and that do ...
Optimal rectangle packing: an absolute placement approach
We consider the problem of finding all enclosing rectangles of minimum area that can contain a given set of rectangles without overlap. Our rectangle packer chooses the x-coordinates of all the rectangles before any of the y-coordinates. We then ...
Determining the minimum-area encasing rectangle for an arbitrary closed curve
This paper describes a method for finding the rectangle of minimum area in which a given arbitrary plane curve can be contained. The method is of interest in certain packing and optimum layout problems. It consists of first determining the minimal-...
Comments