Anpassen der Mindestanzahl von Rechtecken mit Breite / Höhe 1 in ein 2D-Raster

9

Stellen Sie sich ein Problem vor, bei dem Sie ein 2D-Raster (z. B. ein Schachbrett) erhalten, in dem bestimmte Quadrate belegt sind, und Sie müssen die Mindestanzahl nicht überlappender Rechtecke beliebiger Größe wxh mit w = 1 oder h = 1 (dh "Quadrat" angeben Segmente ") so, dass alle nicht besetzten Quadrate bedeckt sind und jedes Rechteck nur unbesetzte Quadrate bedeckt.

Zum Beispiel für das Raster

..###
.....
..###
.#...

Die Lösung wäre 4, da Sie alle nicht besetzten Quadrate (mit '.' bezeichnet) mit 4 solchen Rechtecken wie folgt abdecken können:

12###
12333
12###
1#444

Ich habe versucht, einen Polynomalgorithmus zu entwickeln oder zu beweisen, dass dieses Problem NP-schwer ist, aber ohne Erfolg. Kann mir jemand helfen, zu beweisen / zu widerlegen, dass dieses Problem in P liegt, oder mich auf verwandte Arbeiten / Probleme hinweisen?

eold
quelle
2
Können Rechtecke auch besetzte Quadrate bedecken? Können sich Rechtecke auch überlappen? Die Art und Weise, wie Sie die Lösung des Beispiels vorgestellt haben, legt nahe, dass beides nicht zulässig ist, Ihre Problemstellung jedoch keine Einschränkung enthält.
Tsuyoshi Ito
Richtig, beides ist nicht erlaubt. Ich werde die Problemstellung aktualisieren.
Eold
stackoverflow.com/questions/8639154/…
Ciro Santilli 法轮功 at 病毒 审查 六四 法轮功

Antworten:

11

Ok, Sie haben also ein Polygon mit ganzzahligen, achsparallelen Seiten und möglicherweise mit Löchern (die Form, die Sie abdecken möchten) und möchten es in so wenige 1 × a- oder b × 1- Rechtecke wie möglich unterteilen. Zuerst dachte ich, Sie wollten die minimale Partition in Rechtecke beliebiger Formen, die eine bekannte Polynomzeitlösung aufweist, die eine Reduktion auf maximale unabhängige Mengen in zweigeteilten Graphen beinhaltet. Aber ich denke, dieses ist auch polynomisch, durch eine andere Reduktion auf das gleiche Problem.P.1×einb×1

GP.P.GvGsvs

R.=S.- -ichR.S.P.ichichS.R.ichP.GGist ein zweigeteilter Graph (horizontale Segmente grenzen nur an vertikale Segmente und umgekehrt), so dass seine maximale unabhängige Menge in Polynomzeit gefunden werden kann (siehe König-Theorem auf Wikipedia).

David Eppstein
quelle