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:
- Bedecken eines orthogonalen Polygons mit Quadraten - ähnlich wie bei meinem Problem, aber die Abdeckquadrate dürfen sich überlappen. Dieses Problem hat eine polynomielle Lösung ( Aupperle, Conn, Keil und O'Rourke, 1988 ; Bar-Yehuda und Ben-Hanoch, 1996 ).
- Unterteilen / Zerlegen / Aufteilen eines orthogonalen Polygons in Rechtecke . Dieses Problem hat eine polynomielle Lösung ( Keil, 2000 ; Eppstein, 2009 ).
- Abdecken eines orthogonalen Polygons mit Rechtecken - dieses Problem ist bekanntermaßen NP-vollständig ( Culberson und Reckhow, 1988 ).
Ich suche einen Algorithmus für minimales Kacheln mit Quadraten .
algorithms
computational-geometry
tiling
Erel Segal-Halevi
quelle
quelle
Antworten:
Ich werde versuchen zu zeigen, dass dieses Problem NP-schwer ist, durch Reduktion von .Planar- 3- SAT
Reduktion ausPlanar- 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 :
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.
Links Ein 5X4-Gerät . Mitte und rechts: Zwei mögliche Minimalquadrat-Teilungszustände .
Endpunkt-Gadget
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:
Beispiel:
So wird es verwendet:
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:
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.
Dies lässt jedoch den uneingeschränkten Fall:
Wenn wir zwei I-Drähte kombinieren , können wir eine bidirektionale Implikation erhalten, im Wesentlichen eine boolesche (in) Gleichheit:
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 .
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.
Bilder :
Oben: Ein Draht .
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
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:
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:
Named-Value-Gate
Ein Named-Value-Gate ist im Wesentlichen ein Endpunkt als Gate mit einem Drahtkontakt:
odd-skip-gate : Seltsames Überspringen eines Drahtes
Manchmal ist es unpraktisch, nur Drähte mit ungerader Länge zu verwenden. Beispielsweise:
Wie Sie sehen, ist diese kleine Erweiterung etwas nervig. Hier ist eine entsprechende Lösung unter Verwendung des 4X3-Gatters :
Wenn wir daraus ein Gate machen, erhalten wir das Odd-Skip-Gate (im Drahtgitter):
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:
Überzeugen Sie sich selbst, dass es funktioniert:
Beginne vonEIN Folgen Sie den Pfeiltasten, alles andere sollte erzwungen und konsequent sein.
Das Tor kann nach Bedarf ausgerichtet werden.
split-gate : Draht spalten
Draht teilen, Drahtgitter:
Überzeugen Sie sich davon, dass es funktioniert:
Abbildung: Beginnen Sie mitEIN Folgen Sie den Pfeiltasten. Alles sollte erzwungen und konsequent sein.
Abbildung: Beginnen Sie mitEIN Folgen 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:
Und ein Blick auf die beiden möglichen Zustände:
Das Tor kann nach Bedarf ausgerichtet werden.
Klausel-Tor
Für das Klausel-Gate führen wir zuerst das Klausel-Gadget ein :
Von links nach rechts: 1 Klausel-Gadget . 2-4:3 verschiedene Minimalquadrat-Teilungszustände .
So sieht das Tor aus:
Wir können die verschiedenen Zustände dieses Tores demonstrieren (Erklärung unter allen3 Abbildungen):
Erläuterung:
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
Eine visuelle Hilfe (Originalquelle: Terrain Guarding ist NP-Hard (PDF) , reproduziert in tikz):
Dann:
Warum es funktioniert
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
.quelle
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,
O ( N3 / 2) .
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.
quelle