Mario A. Lopez
Abstract
We present two practical algorithms for partitioning circuit components represented by rectilinear polygons so that they can be stored using the L-shaped corner stitching data structure; that is, our algorithms decompose a simple polygon into a set of nonoverlapping L-shapes and rectangles by using horizontal cuts only. The more general of our algorithms computes and optimal configuration for a wide variety of optimization functions, whereas the other computes a minimum configuration of rectangles and L-shapes. Both algorithms run in O(n + h log h time, where n is the number of vertices in the polygon and h is the number of H-pairs. Because for VLSI data h is small, in practice these algorithms are linear in n. Experimental results on actual VLSI data compare our algorithms and demonstrate the gains in performance for corner stitching (as measured by different objective functions) obtained by using them instead of more traditional rectangular partitioning algorithms.
- BLUST, G. AND MEHTA, D.P. 1993. Corner stitching for L-shaped tiles. In Proceedings of the Third Great Lakes Symposium on VLSI (Kalamazoo, MI, March 5-6), 67-68.Google Scholar
- CAI, Y. AND WONG, D. F. 1993. On minimizing the number of L-shaped channels in 93 building-block layout. IEEE Trans. Comput. Aided Des. 12, 6, 757-769.Google Scholar
- CHAZELLE, B. 1991. Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485-524. Google Scholar
- DAI, W. M., ASANO, T., AND KUH, E. 1985. Routing region definition and ordering scheme for building-block layout. IEEE Trans. Comput. Aided Des. 4, 189-197.Google Scholar
- Du, D. AND ZHANG, Y. 1990. On heuristics for minimum length rectilinear partitions. Algorithmica, 5, 111-128.Google Scholar
- EDELSBRuNNER, H., O'ROURKE, J., AND WELZL, E. 1984. Stationing guards in rectilinear art galleries. Comput. Vision, Graph. Image Process. 27, 167-176.Google Scholar
- GONZALEZ, T. F. AND ZHENG, S.-Q. 1990. Approximation algorithms for partitioning rectilinear polygons. Algorithmica, 5, 11-42.Google Scholar
- GONZALEZ, T. F. AND ZHENG, S.-Q. 1989. Improved bounds for rectangular and guillotine partitions. J. Symbolic Comput. 7 (July), 591-610. Google Scholar
- GONZALEZ, T. F., RAZZAZI, M., SHING, M.-T., AND ZHENG, S.-Q. 1994. On optimal guillotine partitions approximating optimal d-Box partitions. Comput. Geom. Theor. Appl. 4, 1-11. Google Scholar
- GONZALEZ, T. F., RAZZAZI, M., AND ZHENG, S.-Q. 1993. An efficient divide-and-conquer algorithm for partitioning into d-Boxes. Int. J. Comput. Geom. Appl. 3, 4, 417-428.Google Scholar
- HOROWITZ, E., SAHNI, S., AND MEHTA, D. 1995. Fundamentals of Data Structures in C++. Freeman, New York. Google Scholar
- IMAI, H. AND ASANO, T. 1986. Efficient algorithms for geometric graph search algorithms. SIAM J. Comput. 15 (May), 478-494. Google Scholar
- LINGAS, A. 1983. Heuristics for minimum edge length rectangular partitions of rectilinear figures. In Proceedings of the Sixth GI Conference Theoretical Computer Science, vol. 145, Lecture Notes in Computer Science, Springer-Verlag, 199-210. Google Scholar
- LINGAS, A., PINTER, R., RIVEST, R., AND SHAMIR, A. 1982. Minimum edge length partitioning of rectilinear polygons. In Proceedings of the 20th Allerton Conference on Commun. Control Comput., 53-63.Google Scholar
- LIOU, W. T., TAN, J. J. M., AND LEE, R. C. T. 1989. Minimum partitioning of simple rectilinear polygons in O(n loglog n) time. In Proceedings of the Fifth Annual Symposium on Computational Geometry, 344-353. Google Scholar
- MARPLE, D., SMULDERS, M., AND HEGEN, H. 1990. Tailor: A layout system based on trapezoidal corner stitching. IEEE Trans. Comput. Aided Des. 9, 1, 66-90.Google Scholar
- MEHTA, D. P., SHANBHAG, A., AND SHERWANI, N.A. 1995. A new approach for floorplanning in MBC designs. Tech. Rep. 95-02, Univ. of Tennessee Space Institute.Google Scholar
- NAHAR, S. AND SAHNI, S. 1988. A fast algorithm for polygon decomposition. IEEE Trans. Comput. Aided Des. 7 (April), 478-483.Google Scholar
- OHTSUKI, T. 1982. Minimum dissection of rectilinear regions. In Proceedings of the 1982 International Symposium on Circuits and Systems (ISCAS), 1210-1213.Google Scholar
- O'ROURKE, g. 1994. Computational Geometry in C. Cambridge University Press, New York. Google Scholar
- O'ROURKE, g.1983. An alternate proof of the rectilinear art gallery theorem. J. Geom. 21, 118-130.Google Scholar
- OUSTERHOUT, J. K. 1984. Corner stitching: A data structuring technique for VLSI layout tools. IEEE Trans. Comput. Aided Des. 3, 1, 87-100.Google Scholar
- OUSTERHOUT, J., HAMACHI, G., MAYO, R., SCOTT, W., AND TAYLOR, G. 1984. Magic: A VLSI layout system. In Proceedings of the 21st Design Automation Conference, 152-159. Google Scholar
- SEQUIN, C. H. AND FA~ANHA, H. D.S. 1993. Corner stitched tiles with curved boundaries. IEEE Trans. Comput. Aided Des. 12, 1, 47-58.Google Scholar
- SHANBHAG, A. G., DANDA, S. R., AND SHERWANI, N. 1994. Floorplanning for mixed macro block and standard cell designs. In Proceedings of the Fourth Great Lakes Symposium on VLSI (Notre Dame, IN, March 4-5), 26-29.Google Scholar
- SHERWANI, N. 1995. Algorithms for VLSI Physical Design Automation. Kluwer, Boston, MA. Google Scholar
- WANG, T. AND WONG, D.F. 1990. An optimal algorithm for floorplan area optimization. In Proceedings of the 27th Design Automation Conference, 180-186. Google Scholar
- Wu, S. AND SAHNI, S. 1991. Fast algorithms to partition simple rectilinear polygons. Int. J. Comput. Aided VLSI Des. 3, 241-270.Google Scholar
- Wu, S. AND SAHNI, S. 1990. Covering rectilinear polygons by rectangles. IEEE Trans. Comput. Aided Des. 9 (April), 377-388.Google Scholar
- YEAP, K. AND SARRAFZADEH, M. 1993. Floorplanning by graph dualization: 2-Concave rectilinear modules. SIAM J. Comput. 22 (June), 500-526. Google Scholar
Index Terms
- Efficient decomposition of polygons into L-shapes with application to VLSI layouts
Recommendations
An efficient algorithm for partitioning parameterized polygons into rectangles
GLSVLSI '06: Proceedings of the 16th ACM Great Lakes symposium on VLSIIn this paper, we propose an algorithm for partitioning parameterized orthogonal polygons into rectangles. The algorithm is based on the plane-sweep technique and can be used for partitioning polygons which contain holes. The input to the algorithm ...
Ramified Rectilinear Polygons: Coordinatization by Dendrons
Simple rectilinear polygons (i.e. rectilinear polygons without holes or cutpoints) can be regarded as finite rectangular cell complexes coordinatized by two finite dendrons. The intrinsic $$l_1$$l1-metric is thus inherited from the product of the two ...
Estimating the storage requirements of the rectangular and L-shaped corner stitching data structures
This paper proposes a technique for estimating the storage requirements of the Rectangular Corner Stitching (RCS) data structure [Ousterhout 1984] and the L-shaped Corner Stitching (LCS) data structure [Mehta and Blust 1997] on a given circuit by ...
Reviews
Joseph J. O'Rourke
A satisfying connection is made in this paper between work on art gallery theorems, which concerns itself with locating a minimum number of guards to visually cover a polygonal region, and partitioning circuit components for VLSI. One proof of the orthogonal art gallery theorem (which guarantees that no more than n/4 guards are ever needed to cover an orthogonal polygon of n sides) partitions the polygon into L-shaped pieces. (An orthogonal polygon is one whose sides meet at right angles.) Some circuit layout software requires its orthogonal polygon circuit components to be partitioned into L-shaped pieces to match their “corner-stitching” data structure. Where the art gallery work ended with tight combinatorial bounds, the circuit layout community needs fast optimizing software. Lopez and Mehta provide this, with an algorithm for optimal partitioning of orthogonal polygons into L-shaped pieces using only horizontal cuts. Their algorithm is asymptotically O n . They first partition the polygon with cuts containing pairs of horizontally-adjacent reflex vertices, forming an H-graph derived from those used in art gallery work. A postorder traversal of this tree permits enough information to be gathered to support a dynamic programming computation of an optimum partition. The details are intricate (26 cases are considered at one point), but ultimately not that complicated; in any case, all is explained clearly. If one is content with a minimum number of pieces, as opposed to minimizing some other criterion, such as cut length, then a much simpler, greedy algorithm suffices. The authors compare the optimal and greedy algorithms under several criteria on real data sets, and provide clear advice on when the extra coding needed to go beyond the greedy algorithm might be worth the effort (perhaps only for minimizing cut length).
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments