Optimal rectangle packing: an absolute placement approach

摘要: We consider the problem of finding all enclosing rectangles minimum area that can contain a given set without overlap. Our rectangle packer chooses x-coordinates before any y-coordinates. then transform into perfect-packing with no empty space by adding additional rectangles. To determine y-coordinates, we branch on different be placed in each position. allows us to extend known solutions for consecutive-square benchmark from 27 32 squares. also introduce three new benchmarks, avoiding properties make easy, such as shared dimensions. third consists increasingly high precision. pack them efficiently, limit rectangles' coordinates and bounding box dimensions subset sums Overall, our algorithms represent current state-of-the-art this problem, outperforming other orders magnitude, depending benchmark.