Improved Cardinality Bounds for Rectangle Packing Representations

Abstract

Axis-aligned rectangle packings can be characterized by the set of spatial relations that hold for pairs of rectangles (west, south, east, north). A representation of a packing consists of one satisfied spatial relation for each pair. We call a set of representations complete for <i>n</i> ∈ ℕ if it contains a representation of every packing of any <i>n</i> rectangles.<br /> Both in theory and practice, fastest known algorithms for a large class of rectangle packing problems enumerate a complete set <i>R</i> of representations. The running time of these algorithms is dominated by the (exponential) size of <i>R</i>.<br /> In this thesis, we improve the best known lower and upper bounds on the minimum cardinality of complete sets of representations. The new upper bound implies theoretically faster algorithms for many rectangle packing problems, for example in chip design, while the new lower bound imposes a limit on the running time that can be achieved by any algorithm following this approach. The proofs of both results are based on pattern-avoiding permutations.<br /> Finally, we empirically compute the minimum cardinality of complete sets of representations for small <i>n</i>. Our computations directly suggest two conjectures, connecting well-known Baxter permutations with the set of permutations avoiding an apparently new pattern, which in turn seem to generate complete sets of representations of minimum cardinality.