2000•Electronics and Communications in Japan (Part III Fundamental Electronic Science)Requires access
A new approach to rectangle-packing
Akira Nagao, Takashi Sawa, Yuji Shigehiro, Isao Shirakawa, Takashi Kambe
Open publisher page 4 citations
Abstract
The rectangle-packing problem is the problem of placing several given rectangles of arbitrary width and height into a minimum area rectangle without overlapping. This problem can be applied to VLSI packaging design, for which the area significantly affects the fabrication cost. Since this is an NP-hard optimization problem, solutions have been attempted by using heuristic algorithms such as the SA method. The representation of the packing solution is the key to efficiency. Recently, a dramatic representation method of the packing solution called Sequence-Pair has been proposed, so that a high-grade solution can be sought at high speed. In this paper, based on this representation, a high-speed algorithm is proposed that derives rectangle-packing by means of a simple geometrical procedure. It is shown through the evaluation of MCNC benchmark data ami49 that the present algorithm enables high-speed search of a high-grade packing solution even for data with many rectangles. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(12): 94–104, 2000