Rectangle packing
Rectangle packing is a
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 without overlap between any rectangles (small or large). Common constraints of the problem include limiting small rectangle rotation to 90° multiples and requiring that each small rectangle is orthogonal to the large rectangle.
This problem has some applications such as loading of boxes on pallets and, specifically,
Packing identical squares in a rectilinear polygon
Given a rectilinear polygon (whose sides meet at right angles) R in the plane, a set S of points in R, and a set of identical squares, the goal is to find the largest number of non-overlapping squares that can be packed in points of S.
Suppose that, for each point p in S, we put a square centered at p. Let GS be the
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
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.[4]
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.[5][6]
Related problems
- Guillotine cutting is a variant of rectangle packing, with the additional constraint that the rectangles in the packing should be separable using only guillotine cuts.
- Maximum disjoint set (or Maximum independent set) is a problem in which both the sizes and the locations of the input rectangles are fixed, and the goal is to select a largest sum of non-overlapping rectangles. In contrast, in rectangle packing (as in real-life packing problems) the sizes of the rectangles are given, but their locations are flexible. Some papers use the term "packing" even when the locations are fixed.[7]
- Circle packing in a rectangle
- Square packing in a square
- De Bruijn's theorem: packing congruent rectangular bricks of any dimension into rectangular boxes.
References
- S2CID 12718141.
- ISSN 0020-0190.
- S2CID 17190810.
- ^ a b Demaine, Erik (2015). "MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I". Youtube.
- ISSN 1076-9757.
- ^ "Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites". www.codeproject.com. 14 June 2011. Retrieved 2020-09-09.
- .