Biorąc pod uwagę ortogonalny wielokąt (wielokąt, którego boki są równoległe do osi), chcę znaleźć najmniejszy zestaw kwadratów wewnętrznie rozłącznych, których zjednoczenie jest równe wielobokowi.

Znalazłem kilka odniesień do nieco innych problemów, takich jak:

• Pokrycie prostopadłego wielokąta kwadratami - podobnie jak w moim problemie, ale zakrywające kwadraty mogą się pokrywać. Ten problem ma rozwiązanie wielomianowe ( Aupperle, Conn, Keil i O'Rourke, 1988 ; Bar-Yehuda i Ben-Hanoch, 1996 ).
• Układanie płytek / rozkładanie / dzielenie wielokąta ortogonalnego na prostokąty . Ten problem ma rozwiązanie wielomianowe ( Keil, 2000 ; Eppstein, 2009 ).
• Pokrycie ortogonalną wielokąt prostokąty - Problem ten jest znany z NP-zupełny ( Culberson i Reckhow, 1988 ).

Szukam algorytmu minimalnego kafelkowania z kwadratami .

Spróbuję pokazać, że ten problem jest trudny do NP, poprzez redukcję z .$\text{Planar-}3\text{-SAT}$

Redukcja z $\text{Planar-}3\text{-SAT}$

Niektóre podstawowe gadżety

Gadżety to wewnętrzne konfiguracje geometrii, które pozwolą nam budować bramki do użytku w obwodzie, do którego zredukujemy .$\text{Planar-}3\text{-SAT}$

Gadżet 4X3

Ten gadżet ma dwa poprawne stany partycji o minimalnej kwadratowej powierzchni :

^{Po lewej A gadżet 4X3 . Środkowy i prawy: dwa możliwe stany podziału o minimalnym kwadracie .}

Gadżet 5X4

Ten gadżet jest dokładnie taki jak gadżet 4X3 , tylko z większymi wymiarami.

^{Po lewej A gadżet 5X4 . Środkowy i prawy: dwa możliwe stany podziału o minimalnym kwadracie .}

gadżet punktu końcowego

$T$$F$

^{Po lewej: Model szkieletowy gadżetu punktu końcowego . Centrum: prawdziwie wartościowy punkt końcowy. Po prawej: punkt końcowy o fałszywej wartości.}

gadżet i-wire

Gadżet i-wire jest skrótem drutu implikacji .

Zasady:

• $2$$2$
• $3$

Przykład:

^$7$$2$

Oto jak jest używany:

^{Rysunek 8.9 , Left: szkieletowym i-wire w poprzek dwóch punktów końcowych . Po prawej: Unia.}

Teraz, jeśli jeden punkt końcowy jest we właściwym stanie, zmusza drugi punkt końcowy do pozycji wypchniętej. Przykład:

^{Po lewej: kwadratowy schemat podziału; lewy przełącznik jest w dół, „popycha” wszystkie kwadraty w dół i-wire, a na koniec popycha drugi przełącznik ( punkt końcowy ). Po prawej: kwadratowy schemat podziału; lewy punkt końcowy jest pełny, „popycha” wszystkie kwadraty w dół i-wire i wymusza, aby punkt końcowy po lewej stronie był „w górę”.}

$A \implies \neg B$$A \implies B$

Pozostawia to jednak nieograniczony przypadek:

Jeśli połączymy dwa i-przewody , możemy uzyskać dwukierunkową implikację, zasadniczo boolowską (nie) równość:

Tak więc dwa i-przewody mogą przenosić pełną relację równości, podobnie jak obwód - w rzeczywistości jest to obwód. Wykorzystamy te pary do zbudowania użytecznego drutu .

$\frac{l-1}{2}+2$

i-przewody mogą być w razie potrzeby zorientowane.

drut

Przewód składa się parę i-przewodami , które są podłączone do tej samej bramy w każdym punkcie końcowym.

• W I-przewody są w kolorze czerwonym i zielonym.
• $3$
• Każdy bolec bramki będzie miał zielony i czerwony kontakt; przewód musi być prawidłowo podłączony.
• Niezmienna zasada: jeden i-wire należy popchnąć w przeciwnym kierunku niż drugi i-wire , każda bramka przyjmuje to i upewnia się o tym (chyba że zaznaczono inaczej).
• Ponieważ każdy drut zawiera dwukierunkową implikację, przenosi wartości od bramki do bramki jak drut w obwodzie.
• Każdy przewód musi być podłączony do bramki na obu końcach. . W przeciwnym razie może zrujnować założenia niektórych bram, które opisuję, i powyższą niezmienną zasadę; jednak bramy, które mają punkty końcowe na odprowadzeniach, są bezpieczne - możesz podłączyć zbłąkane przewody do tych punktów końcowych, nie martwiąc się o to, że rujnuje bramę.
• przewody muszą mieć nieparzystej długości, w tym przewody do dowolnego obwodu, do którego się podłącza; jednakże poniżej opiszę nieparzystą bramę, która pozwala na uzyskanie nieparzystego drutu.

Zdjęcia :

^{Powyżej: A drutu .}

^{Lewy i prawy: Dwa możliwe stany podziału drutu o minimalnym kwadracie . Pamiętaj, że jeśli drut ma tylko tę długość, nie będzie w stanie przesunąć się w prawo ani w lewo i będzie musiał rozbić jeden kwadrat na mniejsze kawałki.}

przewody mogą być odpowiednio zorientowane.

bend-gate : Gięcie drutu

^{Po lewej: widok siatki. Po prawej: widok Unii.}

Zwróć uwagę na użycie gadżetu 4X3 . Służy do naprawy czerwonego ołowiu na nieparzystej długości.

Poniżej przedstawiono dwa możliwe stany zgięcia o minimalnej kwadratowej powierzchni :

^{Lewy i prawy: Dwa możliwe stany przegięcia drutu o minimalnym kwadracie kwadratowym .}

Bramę można ustawić w razie potrzeby. Oczywiście, ta brama może być dublowana, aby działać w innym kierunku.

Skośny drut

Przesunięcie drutu jest łatwe. Ilustracja modelu szkieletowego:

nazwa-bramki-wartości

Nazwanych wartości brama jest w istocie punkt końcowy jako brama ze stykiem jeden drut:

odd-skip-gate : Dziwne pomijanie drutu

Czasami niewygodne jest posiadanie jedynie drutów o nieparzystej długości. Na przykład:

Jak widać, ta odrobina rozszerzenia jest nieco denerwująca. Oto odpowiednie rozwiązanie przy użyciu bramki 4X3 :

Przekształcając to w bramę, otrzymujemy nieparzystą bramę (w ramce):

Bramę można ustawić w razie potrzeby.

twist-gate : skręcanie drutu

Czasami dostajesz czerwone i czarne i-przewody po niewłaściwych stronach do użycia z bramą . W tym przypadku, skręcenia brama jest, aby skręcać czerwone i czarne i-przewody do przeciwległych stron.

Ilustracja modelu szkieletowego:

Przekonaj się, że to działa:

^$A$

Bramę można ustawić w razie potrzeby.

split-gate : Dzielenie drutu

Podział drutu, szkielet:

Przekonaj się, że to działa:

^$A$

^$A$

Uwaga: Każdy drut wchodzący i wychodzący z rozdzielacza absolutnie musi się gdzieś podłączyć do punktu końcowego, aby zachować niezmienność. Alternatywnie możesz dodać punkty końcowe do każdej pary odprowadzeń rozdzielacza.

Bramę można ustawić w razie potrzeby.

nie-brama

Brama nie bierze drutu i wysyła drut, który ma odwrotne konsekwencje. Zasadniczo jest to bramka obrotowa, z tą różnicą, że znakuje kolory drutów. Te nie-brama wygląda tak:

I widok dwóch możliwych stanów:

Bramę można ustawić w razie potrzeby.

klauzula

W przypadku klauzuli-bramy najpierw wprowadzamy gadżet klauzuli :

^$3$

Oto jak wygląda brama:

$3$

Wyjaśnienie:

2. Zacznij od gadżetu klauzul i postępuj zgodnie ze strzałkami.
3. Brak linii strzałek oznacza, że ​​jest to część obwodu, ale brama nie wprowadza go w stan.
4. Stan gadżetu klauzuli wymusza ocenę jednego z punktów końcowych jako prawdziwego .

$3\text{-CNF}$

Bramę można ustawić w razie potrzeby.

Zmniejszenie

$\Phi(\mathbf x)$$\text{Planar-}3\text{-SAT}$

Pomoc wizualna (oryginalne źródło: Terrain Guarding to NP-Hard (PDF) , reprodukcja w tikz):

Następnie:

1. $x_i\in\mathbf x$$x_i$$\neg x_i$
2. Połącz bramki między sobą bramą , aby logicznie negowały wartości.
3. Umieść wielokąty „bram” zmiennych w ich miejscach w osadzaniu planarnym.
4. Dla każdej klauzuli umieść bramę klauzuli w miejscu klauzuli w osadzeniu planarnym.
5. Korzystając z bramek opisanych powyżej, połącz wszystkie zmienne z ich klauzulami.
6. Uruchom algorytm parowania metodą minimalnych kwadratów na wynikowym połączeniu wszystkich wielokątów bramki (całego obwodu).
7. Jeśli algorytm zwraca sumę wszystkich rozmiarów stanu bramy o minimalnym kwadracie partycji (odejmując dla współdzielonych narożników), jest to zadowalające. Jeśli nie jest zadowalający, zmusi ograniczony gadżet do podziału na mniejsze kwadraty, zwiększając w ten sposób liczbę kwadratów potrzebną do podzielenia obwodu.

Dlaczego to działa?

• Każdy gadżet ma rozmiar stanu partycji o minimalnej kwadratowej powierzchni; to znaczy partycja tego gadżetu o minimalnej kwadratowej powierzchni ma określony rozmiar.
• Niektóre gadżety mają kilka stanów o tym rozmiarze; każdy z tych stanów jest prawidłową partycją o minimalnym kwadracie .
• Gdy gadżety są łączone tylko w rogach, suma stanów podziału z minimalnymi kwadratami podziału gadżetów jest * nadal minimalnym stanem podziału między nimi; widać to intuicyjnie: łączenie w rogu nie zapewnia wystarczającej przestrzeni dla kwadratu do rozwinięcia / połączenia z kwadratem z innego gadżetu.
• Podczas łączenia gadżety na rogu nie zmniejsza całkowity rozmiar minimalny kwadratowych partycji , to nie dotyczą i ograniczyć gadżety ze sobą, nawzajem.
• Z bramkami pokazanymi powyżej, możesz wystarczająco ograniczyć stany, aby jeśli logiczna formuła była niezadowalająca, wówczas jeden lub więcej gadżetów będzie musiał rozbić się na jeszcze mniejsze kwadraty i zwiększyć rozmiar partycji o minimalnym kwadracie .

źródła wykresów

• squaretilings1.tex ( writelatex )
• squaretilings2.tex ( writelatex )
• clausegate.tex ( writelatex )

Większe obrazy można także zobaczyć, usuwając przyrostki „s”, „m”, „l” i adresów URL imgur. Na przykład możesz zobaczyć większy obraz tego: http://i.stack.imgur.com/6CKlGs.jpg , przechodząc do http://i.stack.imgur.com/6CKlG.jpg . Zwróć uwagę na brakujące „s” przed .jpg.

$N$$O(N^{3/2})$

„Pokrycie prostokątów wielokątów kwadratami”. LJ Aupperle i HE Conn, JM Keil i Joseph O'Rourke. Proc. 26th Allerton Conf. Commun Control Comput. , ss. 97-106, 1988. ( link do pobrania skanu PDF )

Jednak powstałe pokrycie może obejmować kwadraty, które się pokrywają. Szukasz kafelków, w których kwadraty nie mogą się pokrywać, więc twój problem nie jest taki sam.