Das Abdecken einfacher orthogonaler Polygone mit Rechtecken

Wir untersuchen das Problem des Abdeckens orthogonaler Polygone mit Rechtecken. Für polynomialzeitliche Algorithmen liegt der beste bekannte Approximationsfaktor bei O (n), wenn das Eingabepolygon Löcher haben kann (Kumar und Ramesh, STOC '99, SICOMP '03), und es ist ein 2-Faktor-Approximation-Algorithmus bekannt, wenn das Polygon lochfrei ist (Franzblau, SIDMA '89). Arguably ist ein einfacher zu lösendes Problem das Boundary Cover-Problem, bei dem wir nur daran interessiert sind, die Grenze des Polygons abzudecken, im Gegensatz zum ursprünglichen Problem, bei dem wir daran interessiert sind, das Innere des Polygons abzudecken, weshalb es auch als Inner Cover-Problem bezeichnet wird. Für das Boundary Cover-Problem ist bekannt, dass ein 4-Faktor-Approximation-Algorithmus existiert, und es ist APX-schwer, wenn das Polygon Löcher hat (Berman und DasGupta, Algorithmica '94). In dieser Arbeit untersuchen wir, wie effektiv ein lokaler Suchalgorithmus für die oben genannten Abdeckungsprobleme bei einfachen Polygonen ist. Wir beweisen, dass ein einfacher lokaler Suchalgorithmus einen PTAS für das Boundary Cover-Problem liefert, wenn das Polygon einfach ist. Unser Beweis beruht auf der Existenz von planaren Unterstützungen auf geeigneten Hypergraphen, die auf der Instanz des Boundary Cover-Problems definiert sind. Andererseits konstruieren wir Instanzen, in denen Unterstützungsgraphen für das Inner Cover-Problem willkürlich große Bikliten haben, was impliziert, dass dieselbe lokale Suchtechnik keinen PTAS für dieses Problem ergeben kann. Wir zeigen auch eine große Lokalitätsspanne für das duale Problem, nämlich das Maximum Antirectangle-Problem.