28 maja 2024 10:15
[Seminarium ZOK] Aniket Basu Roy: Covering Simple Orthogonal Polygons with Rectangles
Abstract:
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 to 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 a large locality
gap for its dual problem, namely the Maximum Antirectangle problem.