Optimal Rectangle Packing: An Absolute Placement Approach
By Eric Huang, Richard E. Korf. 2014
60 citations recorded by the source corpus.
We consider the problem of finding all enclosing rectangles of minimum area that can contain a given set of rectangles without overlap. Our rectangle packer chooses the x-coordinates of all the rectangles before any of the y-coordinates. We then transform the problem into a perfect-packing problem with no empty space by adding additional rectangles. To determine the y-coordinates, we branch on the different rectangles that can be placed in each empty position. Our packer allows us to extend the known solutions for a consecutive-square benchmark from 27 to 32 squares. We also introduce three new benchmarks, avoiding properties that make a benchmark easy, such as rectangles with shared dimensions. Our third benchmark consists of rectangles of increasingly high precision. To pack them efficiently, we limit the rectangles' coordinates and the bounding box dimensions to the set of subset sums of the rectangles' dimensions. Overall, our algorithms represent the current state-of-the-art for this problem, outperforming other algorithms by orders of magnitude, depending on the benchmark.
Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Industrial and Manufacturing Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Graphics and Computer-Aided Design
In Industrial and Manufacturing Engineering
Citations in the corpus
- Towards Better Analysis of Deep Convolutional Neural Networks (2016, methodology): “Each sub-problem can be efficiently solved by the state-of-the-art rectangle packing algorithm [26].”