Kacheln eines orthogonalen Polygons mit Quadraten

12

Bei einem orthogonalen Polygon (ein Polygon, dessen Seiten parallel zu den Achsen sind) möchte ich die kleinste Menge von innen nicht zusammenhängenden Quadraten finden, deren Vereinigung gleich dem Polygon ist.

Ich fand mehrere Hinweise auf leicht unterschiedliche Probleme, wie zum Beispiel:

Ich suche einen Algorithmus für minimales Kacheln mit Quadraten .

Erel Segal-Halevi
quelle
mmm ich kann mir vorstellen, dass das NP-hart ist. Ich werde versuchen, etwas zu formulieren.
Realz Slaw
1
Die Minimierungsversion mit erlaubten Löchern ist NP-Hard, aber für einfach verbundene orthogonale Polygone (dh ohne Löcher) hat sie einen Polynomalgorithmus. Wenn jedoch in Ihrem Problem die Größen ganzzahlig sind und Sie wirklich eine minimale Abdeckung und keine minimale Abdeckung meinen, dann ist in diesem Fall ein Polynomalgorithmus möglich.
Parham
Mmm, ich brauche einen Beweis dafür, dass die Mindestquadrate rational positioniert sind und rationale Größen haben. oder noch mehr, wenn die Eingabe ganzzahlig und ganzzahlig positioniert ist, sind auch die Mindestquadrate (um sie auf SAT zu reduzieren). Ich nehme intuitiv an, dass dies wahr ist. Haben Sie Ideen, um dies zu beweisen?
Realz Slaw
@MahmoudAlimohamadi: Können Sie die Titel / Autoren der Artikel angeben, in denen das Problem des Kachelns von geradlinigen Polygonen (mit oder ohne Löcher) mit Quadraten untersucht (und gelöst) wird ?
Vor dem
2
Übrigens, ich nahm an, Sie meinten "minim um" anstatt "minim al" .
Realz Slaw

Antworten:

15

Ich werde versuchen zu zeigen, dass dieses Problem NP-schwer ist, durch Reduktion von .Planar-3-SAT


Reduktion aus Planar-3-SAT

Einige grundlegende Geräte

Gadgets sind interne Geometriekonfigurationen, mit denen wir Gates zur Verwendung in einer Schaltung konstruieren können, auf die wir reduzieren .Planar-3-SAT

4X3-Gadget

Dieses Gadget verfügt über zwei gültige Minimalquadrat-Partitionszustände :

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Links Ein 4X3-Gadget . Mitte und rechts: Zwei mögliche Minimalquadrat-Teilungszustände .

5X4-Gadget

Dieses Gerät ist genau wie ein 4X3-Gerät , nur mit größeren Abmessungen.

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Links Ein 5X4-Gerät . Mitte und rechts: Zwei mögliche Minimalquadrat-Teilungszustände .

Endpunkt-Gadget

TF

Bildbeschreibung hier eingeben

Links: Drahtmodell des Endpunkt-Gadgets . Mitte: Endpunkt mit wahrem Wert. Richtig: Endpunkt mit falschem Wert.

i-wire Gadget

Ein i-wire-Gadget ist die Abkürzung für Implication Wire .

Regeln:

  • 22 .
  • 3

Beispiel:

Bildbeschreibung hier eingeben

72

So wird es verwendet:

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Abbildung 8.9 , links: Drahtgitter- I-Wire über zwei Endpunkte . Richtig: Union.

Befindet sich nun ein Endpunkt im richtigen Zustand, wird der andere Endpunkt in eine gedrückte Position gebracht. Beispiel:

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Links: Quadratisches Partitionsdiagramm; linker Schalter ist unten, „drückt“ alle Quadrate auf dem i-Draht und schließlich schiebt den anderen Schalter ( Endpunkt ). Rechts: Quadratisches Partitionsdiagramm; Der linke Endpunkt ist voll, "drückt" alle Quadrate auf dem i-wire nach unten und zwingt den linken Endpunkt , "oben" zu sein.

EIN¬BEINB

Dies lässt jedoch den uneingeschränkten Fall:

Bildbeschreibung hier eingeben

Wenn wir zwei I-Drähte kombinieren , können wir eine bidirektionale Implikation erhalten, im Wesentlichen eine boolesche (in) Gleichheit:

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Zwei I-Drähte können also eine vollständige Gleichheitsbeziehung aufweisen, ähnlich wie ein Stromkreis - tatsächlich handelt es sich um einen Stromkreis. Wir werden diese Paare verwenden, um einen verwendbaren Draht zu konstruieren .

l-12+2

i-drähte können nach bedarf ausgerichtet werden.

Draht

Ein Draht besteht aus zwei I-Drähten , die an jedem Endpunkt mit denselben Gattern verbunden sind.

  • Die I-Drähte sind rot und grün gefärbt.
  • 3
  • Jeder Gate-Pin hat einen grünen und einen roten Kontakt. Ein Kabel muss korrekt angeschlossen sein.
  • Invariante Regel: Ein I-Wire wird in die entgegengesetzte Richtung zum anderen I-Wire geschoben, jedes Gate übernimmt dies und stellt dies sicher (sofern nicht anders angegeben).
  • Da jeder Draht eine Zweiwege-Implikation enthält, überträgt er die Werte von Gate zu Gate wie ein Draht in einer Schaltung.
  • Jeder Draht muss an beiden Enden mit einem Tor verbunden werden. . Gelingt dies nicht, können die Annahmen einiger Tore, die ich beschreibe, und die obige Invariantenregel zerstört werden. Gates mit Endpunkten an den Anschlüssen sind jedoch sicher - Sie können Streudrähte an diese Endpunkte anschließen, ohne sich Sorgen machen zu müssen, dass das Gate zerstört wird.
  • Die Drähte müssen ungerade lang sein, einschließlich der Leitungen zu allen Stromkreisen, an die sie angeschlossen sind. Im Folgenden werde ich jedoch ein ungerades Sprungtor beschreiben , mit dem ein gerader Draht ungerade lang werden kann.

Bilder :

Bildbeschreibung hier eingeben

Oben: Ein Draht .

Bildbeschreibung hier eingeben        Bildbeschreibung hier eingeben

Links und rechts: Zwei mögliche Minimalquadrat-Teilungszustände eines Drahtes . Beachten Sie, dass der Draht, wenn er nur diese Länge hat, nicht nach rechts oder links verschoben werden kann und ein Quadrat in kleinere Stücke zerbrechen muss.

Drähte können nach Bedarf ausgerichtet werden.

Biegetor : Biegen eines Drahtes

Bildbeschreibung hier eingeben       Bildbeschreibung hier eingeben

Links: Drahtmodellansicht. Rechts: Union View.

Beachten Sie die Verwendung des 4X3-Gadgets . Es wird verwendet, um das rote Kabel auf eine ungerade Länge zu bringen.

Es folgen die zwei möglichen quadratischen Minimal-Teilungszustände der Biegung:

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Links und rechts: Zwei mögliche Minimalquadratquadrat-Teilungszustände eines Biegedrahtes.

Das Tor kann nach Bedarf ausgerichtet werden. Offensichtlich kann dieses Tor gespiegelt werden, um für die andere Richtung zu arbeiten.

Draht verdrehen

Es ist leicht, einen Draht zu verschieben. Drahtmodell-Abbildung:

Bildbeschreibung hier eingeben

Named-Value-Gate

Ein Named-Value-Gate ist im Wesentlichen ein Endpunkt als Gate mit einem Drahtkontakt:

Bildbeschreibung hier eingeben

odd-skip-gate : Seltsames Überspringen eines Drahtes

Manchmal ist es unpraktisch, nur Drähte mit ungerader Länge zu verwenden. Beispielsweise:

Bildbeschreibung hier eingeben

Wie Sie sehen, ist diese kleine Erweiterung etwas nervig. Hier ist eine entsprechende Lösung unter Verwendung des 4X3-Gatters :

Bildbeschreibung hier eingeben

Wenn wir daraus ein Gate machen, erhalten wir das Odd-Skip-Gate (im Drahtgitter):

Bildbeschreibung hier eingeben

Das Tor kann nach Bedarf ausgerichtet werden.

Twist-Gate : Verdrillen eines Drahtes

Manchmal befinden sich die roten und schwarzen I-Drähte auf der falschen Seite, um mit einem Tor verwendet zu werden . In diesem Fall ist ein Twist-Gate vorgesehen, um die roten und schwarzen I-Drähte zu verdrillen zu den gegenüberliegenden Seiten .

Drahtmodell-Abbildung:

Bildbeschreibung hier eingeben

Überzeugen Sie sich selbst, dass es funktioniert:

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Beginne von EINFolgen Sie den Pfeiltasten, alles andere sollte erzwungen und konsequent sein.

Das Tor kann nach Bedarf ausgerichtet werden.

split-gate : Draht spalten

Draht teilen, Drahtgitter:

Bildbeschreibung hier eingeben

Überzeugen Sie sich davon, dass es funktioniert:

Bildbeschreibung hier eingeben

Abbildung: Beginnen Sie mitEINFolgen Sie den Pfeiltasten. Alles sollte erzwungen und konsequent sein.

Bildbeschreibung hier eingeben

Abbildung: Beginnen Sie mitEINFolgen Sie den Pfeiltasten. Alles sollte erzwungen und konsequent sein.

Hinweis: Jeder Draht, der in den Verteiler hinein- und aus ihm herauskommt, muss unbedingt vorhanden sein mit einem Endpunkt verbunden sein, um die Invariante aufrechtzuerhalten. Alternativ können Sie jedem Leitungspaar des Splitters Endpunkte hinzufügen.

Das Tor kann nach Bedarf ausgerichtet werden.

Nicht-Tor

Das Not-Gate nimmt einen Draht und gibt einen Draht aus, der die umgekehrten Auswirkungen hat. Grundsätzlich handelt es sich um ein Twist-Gate , mit der Ausnahme, dass es die Farben der Drähte neu kennzeichnet. Das Not-Gate sieht so aus:

Bildbeschreibung hier eingeben

Und ein Blick auf die beiden möglichen Zustände:

Bildbeschreibung hier eingeben         Bildbeschreibung hier eingeben

Das Tor kann nach Bedarf ausgerichtet werden.

Klausel-Tor

Für das Klausel-Gate führen wir zuerst das Klausel-Gadget ein :

Bildbeschreibung hier eingeben

Von links nach rechts: 1 Klausel-Gadget . 2-4: 3verschiedene Minimalquadrat-Teilungszustände .

So sieht das Tor aus:

Wir können die verschiedenen Zustände dieses Tores demonstrieren (Erklärung unter allen 3 Abbildungen):

Erläuterung:

  1. Beginnen Sie mit dem Klausel-Gadget und folgen Sie den Pfeilen.
  2. Nicht-Pfeillinien bedeuten, dass es Teil eines Stromkreises ist, aber nicht durch das Tor in einen Zustand gezwungen wird.
  3. Der Status des Klausel-Gadgets erzwingt, dass einer der Endpunkte als wahr bewertet wird .

Wie Sie sehen, muss mindestens eine der Eingaben als wahr bewertet werden . Das ist genau das, was a3-CNF Klausel erfordert.

Das Tor kann nach Bedarf ausgerichtet werden.

Die Ermäßigung

Lassen Φ(x) sei ein Planar-3-SAT Formel, wo

Φ(x)=ichnCich,C={(xjxkxl)}

Eine visuelle Hilfe (Originalquelle: Terrain Guarding ist NP-Hard (PDF) , reproduziert in tikz):

Bildbeschreibung hier eingeben

Dann:

  1. Für jede Variable xichx, platziere zwei benannte-variable-Tore nebeneinander, benenne eines von ihnenxich und der andere ¬xich.
  2. Verbinden Sie die Gates mit einem Nicht-Gate miteinander , so dass sie die Werte des anderen logisch negieren.
  3. Platzieren Sie die Polygone der Variablen "Gates" an ihren Positionen in der planaren Einbettung.
  4. Platzieren Sie für jede Klausel ein Klausel-Gate an der Position der Klausel in der planaren Einbettung.
  5. Verbinden Sie mit den oben beschriebenen Gates alle Variablen mit ihren Klauseln.
  6. Führen Sie einen Minimum-Square-Paritioning-Algorithmus für die resultierende Vereinigung aller Polygone des Gates (der gesamten Schaltung) aus.
  7. Wenn der Algorithmus die Summe aller minimalen quadratischen Partitionszustandsgrößen des Gatters zurückgibt (Subtrahieren für gemeinsame Ecken), ist er erfüllbar. Wenn dies nicht befriedigend ist, wird ein eingeschränktes Gadget gezwungen, sich in kleinere Quadrate aufzuteilen, wodurch die Anzahl der zum Aufteilen der Schaltung erforderlichen Quadrate erhöht wird.

Warum es funktioniert

  • Jedes Gadget hat eine minimale Größe für den quadratischen Partitionsstatus . Das heißt, eine Minimalquadrat-Partition dieses Gadgets hat eine bestimmte Größe.
  • Einige Minianwendungen haben mehrere Status mit dieser Größe. Jeder dieser Zustände sind gültige Minimalquadrat-Partitionen .
  • Wenn Minianwendungen nur in den Ecken kombiniert werden, ist die Summe der minimalen quadratischen Teilungszustände der Minianwendungen * immer noch der minimale quadratische Teilungszustand der Vereinigung von ihnen; Sie können dies intuitiv sehen: Wenn Sie an der Ecke verbinden, hat ein Quadrat nicht genügend Platz, um es zu erweitern bzw. mit einem Quadrat eines anderen Gadgets zu verbinden.
  • Das Kombinieren von Minianwendungen an der Ecke verringert zwar nicht die Gesamtgröße der quadratischen Mindestpartition , beschränkt jedoch die Beziehung zwischen den Minianwendungen.
  • Mit den oben gezeigten Gates können Sie die Zustände ausreichend einschränken, sodass ein oder mehrere Gadets in noch kleinere Quadrate zerfallen und die Partitionsgröße für das Minimum an Quadraten erhöhen müssen, wenn die logische Formel nicht erfüllt werden kann .

Graphquellen

Sie können auch größere Bilder sehen, indem Sie die Suffixe "s", "m", "l" der imgur-URLs entfernen. Zum Beispiel können Sie ein größeres Bild davon sehen: http://i.stack.imgur.com/6CKlGs.jpg, indem Sie http://i.stack.imgur.com/6CKlG.jpg aufrufen . Beachten Sie die fehlenden "s" vor dem .jpg.

Realz Slaw
quelle
3
Wow, das ist absolut beeindruckend. Leider bin ich nicht schlau genug, um die Reduzierung zu überprüfen, aber ich nehme Ihr Wort dafür :) Danke!
Erel Segal-Halevi
1
Die Situation beim Fliesen ist also das Gegenteil der Situation beim Bedecken: Beim Bedecken ist die quadratische Bedeckung polynomisch und die rechteckige Bedeckung NP-hart, während beim Fliesen die quadratische Bedeckung NP-hart und die rechteckige Bedeckung polynomisch ist.
Erel Segal-Halevi
8

Ein altes Papier, das ich mitautorisiert habe, belegt, dass das Deckungsproblem für ein Polygon ohne Löcher polynomisch und NP-vollständig mit Löchern ist. Wir haben gezeigt, dass ein grundlegender Graph akkordisch ist. Bitte beachten Sie: Der Algorithmus ist in der Zahl polynomischN von Einheitsquadraten im Polygon, Ö(N3/2).

"Orthogonale Polygone mit Quadraten bedecken." LJ Aupperle und HE Conn und JM Keil und Joseph O'Rourke. Proc. 26. Allerton Conf. Kommun. Control Comput. , S. 97-106, 1988. ( Link zum Herunterladen des PDF-Scans )

Die resultierende Abdeckung kann jedoch Quadrate enthalten, die sich überlappen. Sie suchen eine Kachelung, bei der sich Quadrate nicht überlappen dürfen, sodass Ihr Problem nicht ganz dasselbe ist.

Joseph O'Rourke
quelle
lol Ich war auf halbem Weg durch eine Formulierung :(. Sehr interessant, aber! Willkommen bei cs.SE.
Realz Slaw
2
Wenn ich das richtig verstehe, lässt dieses Papier zu, dass sich die Quadrate überlappen (dh es ist ein Abdeckungsproblem). Ich interessiere mich für den Fall, dass sich die Quadrate nicht überlappen dürfen (dh es handelt sich um ein Partitionierungs- / Kachelproblem).
Erel Segal-Halevi
@ErelSegalHalevi: Oh, es tut mir leid, ich habe Ihre Frage nicht sorgfältig gelesen.
Joseph O'Rourke
2
Oh, dann
Realz Slaw