  We study the problem of Covering Orthogonal Polygons with Rectangles. For
polynomial-time algorithms, the best-known approximation factor is
$O(\sqrt{\log n})$ when the input polygon may have holes [Kumar and Ramesh,
STOC '99, SICOMP '03], and there is a $2$-factor approximation algorithm known
when the polygon is hole-free [Franzblau, SIDMA '89]. Arguably, an easier
problem is the Boundary Cover problem where we are interested in covering only
the boundary of the polygon in contrast to the original problem where we are
interested in covering the interior of the polygon, hence it is also referred
as the Interior Cover problem. For the Boundary Cover problem, a $4$-factor
approximation algorithm is known to exist and it is APX-hard when the polygon
has holes [Berman and DasGupta, Algorithmica '94].
  In this work, we investigate how effective is local search algorithm for the
above covering problems on simple polygons. We prove that a simple local search
algorithm yields a PTAS for the Boundary Cover problem when the polygon is
simple. Our proof relies on the existence of planar supports on appropriate
hypergraphs defined on the Boundary Cover problem instance. On the other hand,
we construct instances where support graphs for the Interior Cover problem have
arbitrarily large bicliques, thus implying that the same local search technique
cannot yield a PTAS for this problem. We also show large locality gap for its
dual problem, namely the Maximum Antirectangle problem.
