On the number of anchored rectangle packings for a planar point set

We consider packing axis-aligned rectangles r1,…,rn in the unit square [0,1]2 such that a vertex of each rectangle ri is a given point pi (i.e., ri is anchored at pi). We explore the combinatorial structure of all locally maximal configurations. When the given points are the lower-left corners of the rectangles, the number of maximal packings is shown to be at most 2nCn, where Cn is the nth Catalan number. The number of maximal packings remains exponential in n when the points may be arbitrary corners of the rectangles. Both upper bounds are complemented with exponential lower bounds. Finally, we define the graph of all lower-left anchored maximal rectangle packings, where the edges correspond to elementary operations between two packings, which leads to an output sensitive algorithm for computing these packings.