Optimal rectangle packing: an absolute placement approach

DOI10.1613/JAIR.3735MaRDI QIDQ4907833zbMATH OpenOpenAlexFDO

Authors Eric Huang, Richard E. Korf

Publication date 25 February 2013

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.0557

zbMATH Keywords

optimal solutionperfect packing problemrectangle packing

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial optimization (90C27)

Abstract: 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.

Recommendations

• Optimal rectangle packing
• Packing Rectangles into 2OPT Bins Using Rotations
• scientific article; zbMATH DE number 19811
• An optimal algorithm for rectangle placement
• A novel non-linear approach to minimal area rectangular packing

Cited in

(15)

• An optimal algorithm for rectangle placement
• Scheduling under the network of temporo-spatial proximity relationships
• Packing unequal rectangles and squares in a fixed size circular container using formulation space search
• Expected wasted space of optimal simple rectangle packing
• Optimized location of light sources to cover a rectangular region
• Enumerating bottom-left stable positions for rectangle placements with overlap
• Corner occupying theorem for the two-dimensional integral rectangle packing problem
• Parameterized complexity of strip packing and minimum volume packing
• Handling precedence constraints in scheduling problems by the sequence pair representation
• Packing a rectangle with m x (m + 1) rectangles
• Data set generation for rectangular placement problems
• Optimal rectangle packing
• Stabilized branch-and-price algorithms for vector packing problems
• A mathematical model for optimization of vehicle parking space
• A new search procedure for the two-dimensional orthogonal packing problem

This page was built for publication: Optimal rectangle packing: an absolute placement approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4907833)