An Existential Proof of the Conjecture on Packing Anchored Rectangles

2013/10/31 by Banerjee, Sandip, Banik, Aritra, Bhattacharya, Bhargab B. +2
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1310.8403

Abstract

Let P_n be a set of n points, including the origin, in the unit square U = [0,1]². We consider the problem of constructing n axis-parallel and mutually disjoint rectangles inside U such that the bottom-left corner of each rectangle coincides with a point in P_n and the total area covered by the rectangles is maximized \citeibmpuzzle, \citeWinkler2007, \citeWinkler2010a, \citeWinkler2010b. The longstanding conjecture has been that at least half of U can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.

Related

• On Packing Almost Half of a Square with Anchored Rectangles: A Constructive Approach
• Packing anchored rectangles
• Special Configurations in Anchored Rectangle Packings
• A better lower bound for Lower-Left Anchored Rectangle Packing
• Anchored Rectangle and Square Packings