Dado um polígono ortogonal (um polígono cujos lados são paralelos aos eixos), quero encontrar o menor conjunto de quadrados disjuntos do interior, cuja união é igual ao polígono.

Encontrei várias referências a problemas ligeiramente diferentes, como:

• Cobrir um polígono ortogonal com quadrados - semelhante ao meu problema, mas é permitido que os quadrados de cobertura se sobreponham. Esse problema tem uma solução polinomial ( Aupperle, Conn, Keil e O'Rourke, 1988 ; Bar-Yehuda e Ben-Hanoch, 1996 ).
• Lado a lado / decompondo / particionando um polígono ortogonal em retângulos . Esse problema tem uma solução polinomial ( Keil, 2000 ; Eppstein, 2009 ).
• Cobrindo um polígono ortogonal com retângulos - esse problema é conhecido como NP-completo ( Culberson e Reckhow, 1988 ).

Estou procurando um algoritmo para o mínimo de ladrilhos com quadrados .

Vou tentar mostrar que esse problema é NP-difícil, por redução do .$\text{Planar-}3\text{-SAT}$

Redução de $\text{Planar-}3\text{-SAT}$

Alguns gadgets básicos

Gadgets são configurações internas da geometria que nos permitem construir portões para uso em um circuito, ao qual reduziremos o .$\text{Planar-}3\text{-SAT}$

Gadget 4X3

Este gadget possui dois estados mínimos de partição quadrada válidos :

^{Esquerda Um gadget 4X3 . Médio e direito: dois possíveis estados de partição quadrada mínima .}

Gadget 5X4

Este gadget é exatamente como um gadget 4X3 , apenas com dimensões maiores.

^{Esquerda Um gadget 5X4 . Médio e direito: dois possíveis estados de partição quadrada mínima .}

dispositivo de ponto final

Um dispositivo de ponto final é um dispositivo 5X4 . É freqüentemente usado como um ponto final / pino de uma porta . Um dos dois estados de um terminal pode ser avaliado como verdadeiro e o outro falso. Um ponto de extremidade marcas das duas extremidades, uma de eo outro como F . O fim coberto pelo quadrado grande é o valor do ponto final.$T$$F$

^{Esquerda: estrutura de arame do dispositivo de extremidade . Centro: ponto final com valor real. Direita: Ponto final com valor falso.}

dispositivo i-wire

Um dispositivo i-wire é a abreviação de fio de implicação .

Regras:

• Um dispositivo i-wire consiste em um retângulo de comprimento ímpar com mais de e largura 2 .$2$$2$
• Um dispositivo i-wire pode ter estados de partição quadrada mínima , empurrados de um lado, do outro ou de nenhum dos dois; um i-wire neste terceiro estado deve ser chamado localmente sem restrições .$3$

Exemplo:

^{Figura 7: Um dispositivo de i-wire de comprimento e largura 2 .$7$$2$}

Aqui está como é usado:

^{Figura 8,9 , Esquerda: estrutura de arame i-wire em dois pontos finais . Direita: União.}

Agora, se um ponto final estiver no estado correto, ele forçará o outro ponto final a uma posição empurrada. Exemplo:

^{Esquerda: diagrama de partição quadrado; o interruptor esquerdo está pressionado, "empurra" todos os quadrados para baixo no fio i e, finalmente, empurra o outro interruptor ( ponto final ). Direita: Diagrama de partição quadrado; o ponto final esquerdo está cheio "empurra" todos os quadrados para baixo do i-wire e força o ponto final à esquerda a "subir".}

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

No entanto, isso deixa o caso irrestrito:

Se combinarmos dois i-fios , podemos obter uma implicação bidirecional, essencialmente uma igualdade (in) booleana:

Portanto, dois i-fios podem ter uma relação de igualdade completa, como um circuito - na verdade, é um circuito. Usaremos esses pares para construir um fio utilizável .

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

os fios i podem ser orientados conforme necessário.

fio

Um fio consiste em um par de fios i conectados aos mesmos portões em cada ponto final.

• Os fios i são coloridos de vermelho e verde.
• $3$
• Cada pino de porta terá um contato verde e vermelho; um fio deve conectar corretamente.
• Regra invariável: um fio i é empurrado na direção oposta do outro fio i , cada porta assume isso e garante isso (a menos que seja indicado de outra forma).
• Como cada fio contém uma implicação bidirecional, ele carrega os valores de porta em porta como um fio em um circuito.
• Todo fio deve ser conectado a um portão nas duas extremidades. . Se isso não for feito, pode arruinar as suposições de alguns portões que descrevo e a regra invariável acima; no entanto, portões que têm pontos de extremidade nos condutores são seguros - você pode conectar fios perdidos a esses pontos de extremidade sem se preocupar em arruinar o portão.
• os fios devem ter um comprimento ímpar, incluindo os condutores de qualquer circuito ao qual ele se conecta; no entanto, descreverei um pulo ímpar abaixo, que permite que um fio de comprimento par se torne de comprimento ímpar.

Imagens :

^{Acima: Um fio .}

^{Esquerda e direita: dois possíveis estados de partição mínima quadrada de um fio . Observe que, se o fio tiver apenas esse comprimento, ele não poderá se deslocar para a direita ou para a esquerda e precisará quebrar um quadrado em pedaços menores.}

os fios podem ser orientados conforme necessário.

dobrar-portão : dobrar um fio

^{Esquerda: Vista da estrutura de arame. Direita: visão da União.}

Observe o uso do gadget 4X3 . É usado para fixar o fio vermelho em um comprimento ímpar.

A seguir, estão os dois possíveis estados de partição quadrada mínima da dobra:

^{Esquerda e direita: dois possíveis estados de partição mínima quadrada quadrada de um fio dobrado.}

O portão pode ser orientado conforme necessário. Obviamente, esse portão pode ser espelhado para funcionar na outra direção.

Inclinar um fio

É fácil mudar um fio. Ilustração de estrutura de arame:

portão com valor nomeado

Uma porta de valor nomeado é essencialmente um terminal como uma porta com um contato de fio:

odd-skip-gate : Odd skipping a wire

Às vezes, é inconveniente ter apenas fios de comprimento ímpar. Por exemplo:

Como você pode ver, esse pequeno pedaço de extensão é um pouco chato. Aqui está uma solução correspondente, usando o 4X3-gate :

Então, transformando isso em um portão, obtemos o ímpar-pular-portão (em estrutura de arame):

O portão pode ser orientado conforme necessário.

porta de torção : Torcer um fio

Às vezes, você obtém os fios vermelhos e pretos nos lados errados para usar com um portão . Nesse caso, é fornecida uma porta de torção, para torcer os fios vermelhos e pretos para os lados opostos.

Ilustração de estrutura de arame:

Convença-se de que funciona:

^$A$

O portão pode ser orientado conforme necessário.

porta dividida : dividindo um fio

Dividindo um fio, estrutura de arame:

Convença-se de que funciona:

^$A$

^$A$

Nota: Todo fio que entra e sai do divisor deve absolutamente se conectar a um ponto final em algum lugar, a fim de manter a invariante. Como alternativa, você pode adicionar pontos de extremidade a cada um dos pares de derivações do divisor.

O portão pode ser orientado conforme necessário.

não-portão

O portão não pega um fio e gera um fio que tem implicações inversas. É basicamente uma porta de torção , exceto pelo fato de rotular novamente as cores dos fios. O not-gate fica assim:

E uma visão dos dois estados possíveis:

O portão pode ser orientado conforme necessário.

porta-cláusula

Para o clause-gate , primeiro apresentamos o clause-gadget :

^$3$

É assim que o portão se parece:

$3$

Explicação:

2. Comece no gadget de cláusulas e siga as setas.
3. Linhas que não são de seta significam que faz parte de um circuito, mas não é forçado a entrar em um estado pelo portão.
4. O estado do dispositivo de cláusula força um dos terminais a ser avaliado como verdadeiro .

$3\text{-CNF}$

O portão pode ser orientado conforme necessário.

Redução

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

Um auxílio visual (fonte original: Terrain Guarding é NP-Hard (PDF) , reproduzido em tikz):

Então:

1. $x_i\in\mathbf x$$x_i$$\neg x_i$
2. Conecte os portões um ao outro com um não-portão , para que eles logicamente negem os valores um do outro.
3. Coloque os polígonos das 'portas' das variáveis ​​em seus locais na incorporação plana.
4. Para cada cláusula, coloque um portão de cláusula no local da cláusula na incorporação plana.
5. Usando os portões descritos acima, conecte todas as variáveis ​​às suas cláusulas.
6. Execute um algoritmo de pareamento mínimo quadrado na união resultante de todos os polígonos do gate (o circuito inteiro).
7. Se o algoritmo retornar a soma de todos os tamanhos de estado da partição quadrada mínima do portão (subtração para cantos compartilhados), será satisfatório. Se não for satisfatório, forçará um gadget restrito a se dividir em quadrados menores, aumentando assim o número de quadrados necessários para particionar o circuito.

Por que funciona

• Cada gadget tem um tamanho mínimo de estado da partição quadrada ; isto é, uma partição quadrada mínima desse gadget é de um determinado tamanho.
• Alguns gadgets têm vários estados com esse tamanho; cada um desses estados são partições mínimas quadradas válidas .
• Quando os gadgets são combinados apenas nos cantos, a soma dos estados de partição quadrada mínima dos gadgets é * ainda o estado mínimo de partição quadradaUM da união deles; você pode ver isso intuitivamente: a união na esquina não oferece amplo espaço para um quadrado expandir / conectar-se a um quadrado de outro gadget.
• Ao combinar dispositivos no canto não diminui o tamanho total de quadrados mínimos partição- , que se referem e restringir os aparelhos com cada-outro.
• Com os portões mostrados acima, você pode restringir os estados o suficiente, de modo que, se a fórmula lógica for insatisfatória, um ou mais gadgets terão que quebrar em quadrados ainda menores e aumentar o tamanho mínimo da partição quadrada .

fontes gráficas

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

Você também pode ver imagens maiores removendo os sufixos "s", "m", "l", dos URLs de imgur. Por exemplo, você pode ver uma imagem maior disso: http://i.stack.imgur.com/6CKlGs.jpg , acessando http://i.stack.imgur.com/6CKlG.jpg . Observe os "s" ausentes antes do .jpg.

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

"Cobrindo polígonos ortogonais com quadrados." LJ Aupperle e HE Conn e JM Keil e Joseph O'Rourke. Proc. 26ª Allerton Conf. Comum. Control Comput. , pp. 97-106, 1988. ( link para download da digitalização em PDF )

No entanto, a cobertura resultante pode incluir quadrados que se sobrepõem. Você está procurando um ladrilho, onde os quadrados não podem se sobrepor, portanto seu problema não é exatamente o mesmo.