A new approach to rectangle-packing

✍ Scribed by Akira Nagao; Takashi Sawa; Yuji Shigehiro; Isao Shirakawa; Takashi Kambe

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 957 KB
• Volume: 83
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/1520-6440(200012)83:12<94::aid-ecjc11>3.0.co;2-d

✦ Synopsis

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 rectanglepacking 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.