Abstrac We review several algorithms that can be used to solve the problem of packing rectangles into two-dimensional nite bins. Most of the pre- sented algorithms have well been studied in literature, but some of the variants are less known and some are apparently regarded as “folklore” and no previous reference is known. Di erent variants are presented and compared. The main contribution of this survey is an original classi cation of these variants from the viewpoint of solving the nite bin packing problem. This work focuses on empirical studies on the problem variant where rectangles are placed orthogonally and may be rotated by 90 degrees. Synthetic tests are used as the main benchmark and solving a practical problem of generating texture atlases is used to test the real-world performance of each method. As a related contribu- tion, an original proof concerning the number of maximal orthogonal rectangles inside a rectilinear polygon is presented
Keywords: Two-dimensional bin packing, optimization, heuristic algo- rithm, on-line algorithm, NP-hard
Jukka Jylänki
February 27, 2010
View source: