ABSTRACT
The layout problem requires a combination of space costs and communication costs to be minimized. The special problem of planar, rectangular spaces occurs, for example, in floor plans for electronic planar packages and for buildings.
Here we describe a number of algorithms, embedded in an interactive system, that solve the layout problem efficiently when it is expressed in terms of the package planning algorithm. A hierarchical approach is used to contain computational growth.
- 1.W. R. Heller, "An Algorithm for Chip Planning," Caltech Silicon Structures Project Memo 2806, May 1979.Google Scholar
- 2.W. R. Heller, "Wirability of Logic Packages in LSI and VLSI," IEEE COMPSAC III Proceedings, Nov, 1979.Google Scholar
- 3.W. R. Heller, G. Sorkin and K. Maling, "The Planar Package Planner for System Designers," Proceedings of the Nineteenth Design Automation Conference, 1982. Google ScholarDigital Library
- 4.C. S. Horng and M. Lie, "An Automatic/Interactive Layout Planning System for Arbitrarily-Sized Rectangular Building Block," Proceedings of the Eighteenth Design Automation Conference, 1981. Google ScholarDigital Library
- 5.P. Galle, "An Algorithm for Exhaustive Generation of Building Floor Plans," Comm. ACM, Vol. 24, No. 12, December 1981. Google ScholarDigital Library
- 6.B. T. Preas and W. M. vanCleemput, "Placement Algorithms for Arbitrarily Shaped Blocks," Proceedings of the Sixteenth Design Automation Conference, 1979. Google ScholarDigital Library
- 7.G. B. Dantzig, "Linear Programming and Extensions," Princeton University Press, 1963.Google Scholar
- 8.G. D. Hachtel, T. R. Scott and R. P. Zug, "An Interactive, Linear Programming Approach to Model Parameter Fitting and Worst Case Circuit Design," IEEE Transactions on Circuits and Systems, Vol. CAS-27, No. 10, October 1980.Google Scholar
Index Terms
- On finding most optimal rectangular package plans
Recommendations
Finding the Maximum Empty Axis-Parallel Rectangular Annulus
Combinatorial Image AnalysisAbstractAn annulus is basically a ring-shaped region between two concentric disks on the same plane. However, it can be defined on any other geometrical shapes, for example, a rectangular annulus is defined as the area between two rectangles with one ...
Area-universal rectangular layouts
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometryA rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. They are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are ...
Area-Universal and Constrained Rectangular Layouts
A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. These layouts are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often ...
Comments