Rectangle Covers Revisited Computationally

Laura Heinrich-Litan and Marco E. Lübbecke

Orthogonal polygon; rectangle cover; integer program; approximation algorithm

We consider the problem of covering an orthogonal polygon with a minimum number of axis-parallel rectangles from a computational point of view. Our integer programming formulation is the first approach to solve this NP-hard problem optimally. In experiments it turns out that the linear programming relaxation is extremely tight. Making use of the dual program, we propose a new lower bound on the optimum, namely the cardinality of a fractional stable set. We obtain excellent experimental results for polygons originating from VLSI design, fax data sheets, black and white images, and for random instances. We believe that our proposals have a strong potential to settle the main open problem in the area: To find a constant factor approximation algorithm for the rectangle cover problem.

Download as [PDF] [ps.gz]