Guillotine cutting is asymptotically optimal for packing consecutive squares

Abstract

More than half a century ago Martin Gardner popularized a question leading to the benchmark problem of determining the minimum side length of a square into which the squares of sizes 1, 2,..., n can be packed without overlap. Constructions are known for a certain range of n, and summing up the areas yields that a packing in a square of size smaller than N :=√n(n + 1)(2n + 1)/6) is not possible. Here we prove that an asymptotically minimal packing exists in a square of size N +cn+O(√n) with c < 1, and such a packing is achievable with guillotine-cuts. An improved construction is also given for the case where the constraint of guillotine cutting is dropped. Keywords: Square packing · Guillotine cut · Asymptotic analysis · Gardner’s problem · Square the square · Recursive algorithm.