| Abstract | |
We consider the problem of covering an orthogonal polygon with a
minimum number of axis-parallel rectangles from a computational
point of view. We propose an integer program which is the first
general approach to obtain provably optimal solutions to this
well-studied NP-hard problem. It applies to common variants like
covering only the corners or the boundary of the polygon, and also
to the weighted case. In experiments it turns out that the linear
programming relaxation is extremely tight, and rounding a fractional
solution is an immediate high quality heuristic. We obtain
excellent experimental results for polygons originating from VLSI
design, fax data sheets, black and white images, and for random
instances. Making use of the dual linear program, we propose a
stronger lower bound on the optimum, namely the cardinality of a
fractional stable set. We outline ideas how to make use of this
bound in primal-dual based algorithms. We give partial results which
make us 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.
|