Rectangle packing is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large rectangle, such that no two small rectangles overlap. Several variants of this problem have been studied.
Packing identical rectangles in a rectangle
In this variant, there are multiple instances of a single rectangle of size (l,w), and a bigger rectangle of size (L,W). The goal is to pack as many small rectangles as possible into the big rectangle. It is allowed to rotate some of the small rectangles by multiples of 90°.
This problem has some such as loading of boxes on pallets and, specifically, woodpulp stowage. As an example result: it is possible to pack 147 small rectangles of size (137,95) in a big rectangle of size (1600,1230).[1]
Packing different rectangles in a given rectangle
In this variant, the small rectangles can have varying lengths and widths, and they should be packed in a given large rectangle. The decision problem of whether such a packing exists is NP-hard. This can be proved by a reduction from 3-partition. Given an instance of 3-partition with 3m positive integers: a1, ..., a3m, with a total sum of m T, we construct 3m small rectangles, all with a width of 1, such that the length of rectangle i is ai + m. The big rectangle has width m and length T + 3m. Every solution to the 3-partition instance induces a packing of the rectangles into m subsets such that the total length in each subset is exactly T, so they exactly fit into the big rectangle. Conversely, in any packing of the big rectangle, there must be no "holes", so the rectangles must not be rotated. Therefore, the packing must involve exactly m rows where each row contains rectangles with a total length of exactly T. This corresponds to a solution of the 3-partition instance.[2][3]
When there is an additional restriction that the packing must be exact (with no wasted space), the small rectangles may be rotated only by multiples of 90°. In this case, the problem is in NP. Without this requirement, the small rectangles may be rotated in arbitrary angles. In this more general case, it is not clear if the problem is in NP, since it is much harder to verify a solution.[3]
Packing different rectangles in a minimum-area rectangle
In this variant, the small rectangles can have varying lengths and widths, and their orientation is fixed (they cannot be rotated). The goal is to pack them in an enclosing rectangle of minimum area, with no boundaries on the enclosing rectangle's width or height. This problem has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is NP-complete in general, but there are fast algorithms for solving small instances.[4][5]
See also
Guillotine problem
Square packing in a square
De Bruijn's theorem
References
Birgin, E G; Lobato, R D; Morabito, R (2010). "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle". Journal of the Operational Research Society. 61 (2): 306–320. doi:10.1057/jors.2008.141. S2CID 12718141.
Demaine, Erik D.; Demaine, Martin L. (2007-06-01). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23 (1): 195–208. doi:10.1007/s00373-007-0713-4. ISSN 1435-5914.
Demaine, Erik (2015). "MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I". Youtube.
Huang, E.; Korf, R. E. (2013-01-23). "Optimal Rectangle Packing: An Absolute Placement Approach". Journal of Artificial Intelligence Research. 46: 47–87. doi:10.1613/jair.3735. ISSN 1076-9757.
"Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites". www.codeproject.com. Retrieved 2020-09-09.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
