Mosaico de um polígono ortogonal com quadrados

12

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:

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

Erel Segal-Halevi
fonte
mmm Eu posso imaginar isso sendo NP-difícil. Vou tentar formular alguma coisa.
Realz Slaw
1
A versão de minimização com furos permitidos é NP-Hard, mas para polígonos ortogonais simplesmente conectados (ou seja, sem furos), ele possui um algoritmo polinomial. No entanto, se no seu problema os tamanhos são inteiros e você realmente quer dizer uma cobertura mínima e não uma cobertura mínima, nesse caso, um algoritmo polinomial é possível.
Parham
Mmm, eu preciso de uma prova de que os quadrados mínimos serão racionalmente posicionados e terão tamanhos racionais; ou ainda mais, que se a entrada tiver tamanho inteiro e posição inteira, os quadrados mínimos também serão (para reduzi-la a SAT). Intuitivamente, suponho que isso seja verdade, você tem alguma idéia para provar isso?
Realz Slaw
@MahmoudAlimohamadi: você pode fornecer os títulos / autores do documento (s) onde o problema da telha polígonos retilíneas (com ou sem buracos) com quadrados é estudadas (e resolvidos).
Vor
2
btw, eu assumi que você quis dizer minim um ao invés de minim al .
Realz Slaw

Respostas:

15

Vou tentar mostrar que esse problema é NP-difícil, por redução do .Planar-3-SENTOU


Redução de Planar-3-SENTOU

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 .Planar-3-SENTOU

Gadget 4X3

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

insira a descrição da imagem aqui         insira a descrição da imagem aqui         insira a descrição da imagem aqui

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.

insira a descrição da imagem aqui         insira a descrição da imagem aqui         insira a descrição da imagem aqui

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.TF

insira a descrição da imagem aqui

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 .22
  • 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:

insira a descrição da imagem aqui

Figura 7: Um dispositivo de i-wire de comprimento e largura 2 .72

Aqui está como é usado:

insira a descrição da imagem aqui         insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui         insira a descrição da imagem aqui

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".

UMA¬BUMAB

No entanto, isso deixa o caso irrestrito:

insira a descrição da imagem aqui

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

insira a descrição da imagem aqui         insira a descrição da imagem aqui

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 .

eu-12+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 :

insira a descrição da imagem aqui

Acima: Um fio .

insira a descrição da imagem aqui        insira a descrição da imagem aqui

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

insira a descrição da imagem aqui       insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui         insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui

portão com valor nomeado

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

insira a descrição da imagem aqui

odd-skip-gate : Odd skipping a wire

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

insira a descrição da imagem aqui

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

insira a descrição da imagem aqui

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

insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui

Convença-se de que funciona:

insira a descrição da imagem aqui         insira a descrição da imagem aqui

UMA

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

porta dividida : dividindo um fio

Dividindo um fio, estrutura de arame:

insira a descrição da imagem aqui

Convença-se de que funciona:

insira a descrição da imagem aqui

UMA

insira a descrição da imagem aqui

UMA

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:

insira a descrição da imagem aqui

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

insira a descrição da imagem aqui         insira a descrição da imagem aqui

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

porta-cláusula

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

insira a descrição da imagem aqui

3

É assim que o portão se parece:

3

Explicação:

  1. Comece no gadget de cláusulas e siga as setas.
  2. 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.
  3. O estado do dispositivo de cláusula força um dos terminais a ser avaliado como verdadeiro .

3-CNF

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

Redução

Φ(x)Planar-3-SENTOU

Φ(x)=EunCEu,C={(xjxkxeu)}

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

insira a descrição da imagem aqui

Então:

  1. xEuxxEu¬xEu
  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

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.

Realz Slaw
fonte
3
Uau, isso é absolutamente impressionante. Infelizmente, não sou inteligente o suficiente para verificar a redução, mas confio na sua palavra :) Obrigado!
precisa
1
Portanto, a situação no ladrilho é o oposto da situação no revestimento: no revestimento, a cobertura quadrada é polinomial e a cobertura retangular é NP-difícil, enquanto no ladrilho, a cobertura quadrada é NP-resistente e a cobertura retângulo é polinomial.
precisa
8

NO(N3/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.

Joseph O'Rourke
fonte
lol Eu estava no meio de uma formulação :(. Muito interessante! Bem-vindo ao cs.SE.
Realz Slaw
2
Se bem entendi, este artigo permite que os quadrados se sobreponham (isto é, é um problema de cobertura). Estou interessado no caso em que os quadrados não podem se sobrepor (ou seja, é um problema de particionamento / lado a lado).
Erel Segal-Halevi 04/11
@ErelSegalHalevi: Desculpe, não li sua pergunta com atenção.
Joseph O'Rourke
2
Ah, então vou continuar: D
Realz Slaw