Complexidade do quebra-cabeça polígono oculto em grades quadradas?

10

Hiroimono é um quebra-cabeça completo de popular . Estou interessado na complexidade computacional de um quebra-cabeça relacionado.NP

O problema é:

Entrada : Dado um conjunto de pontos em em um x grade quadrada e inteiron knnk

Pergunta : Existe um polígono retilíneo (seus lados paralelos ao eixo ou ) tal que o número de pontos nos cantos do polígono seja pelo menos ?y kxyk

Cada canto do polígono deve estar em um dos pontos de entrada (portanto, as dobras são permitidas apenas em um ponto de entrada).

Qual é a complexidade desse problema? Qual é a complexidade se a solução é restrita a polígonos retilíneos convexos?

EDIT 13 de abril: formulação alternativa: encontre um polígono retilíneo com os cantos máximos nos pontos indicados.

Mohammad Al-Turkistany
fonte
4
Os polígonos retilíneos convexos não deveriam ser solucionáveis ​​em tempo polinomial pela programação dinâmica?
Peter Shor
4
Sim deveria.
Jeffε
@ Jeff, como sobre o caso geral não convexo? Qual é a sua inclinação?
Mohammad Al-Turkistany
2
para muitos desses problemas, sua melhor aposta é começar com algo como o 3SAT plano ou até o NAE-SAT plano. Será horrivelmente feio, mas a planaridade fornece as estruturas que você pode precisar.
Suresh Venkat #:
5
@Suresh Apenas uma observação: pesquisando ao redor, descobri que a versão planar do NAE3SAT está em P ( portal.acm.org/… ).
Marzio De Biasi

Respostas:

6

Pensei nessa redução estranha (as chances de estar errado são altas :-). Idéia: redução do caminho hamiltoniano em gráficos de grade com grau ; cada nó do gráfico plano pode ser deslocado de tal maneira que cada "linha" ( valor ) e cada "coluna" ( valor ) contenham no máximo um nó. O gráfico pode ser dimensionado e cada nó pode ser substituído por um gadget quadrado com muitos pontos; links horizontais entre os gadgets (as bordas do gráfico original) são feitos usando pares de pontos em linhas distintas, links verticais usando pares de pontos em colunas distintas. As travessias dos nós são forçadas usando os "muitos pontos" dos gadgets quadrados.y x3yx

O gadget do nó é representado na figura a seguir:

insira a descrição da imagem aqui

Possui 3 "pontos de interface" (em colunas / linhas distintas) e uma borda interna de pontos. Uma polilinha que atravessa o gadget de um ponto de interface para outro pode ter um número de cantos proporcional a (três percursos do gadget são mostrados na figura), em particular o número de pontos de canto está entre e (o número total de pontos do gadget é ). O gadget pode ser girado para obter outras combinações de pontos de interface ( , , ).C × C C 2 C 2 C + 2 C × C - 4 + 6 [ N , E , S ] [ E , S , W ] [ S , W , N ][W,N,E]C×CC2C2C+2C×C4+6[N,E,S][E,S,W][S,W,N]

Agora podemos mudar o gráfico da grade planar de tal maneira que, para cada par de nós , e . Veja a figura a seguir de uma grade simples . Em seguida, podemos dimensionar o gráfico e substituir cada nó pelo gadget acima. Nesse estágio, cada gadget é "isolado": uma polilinha não pode ir de um gadget para outro.x 1x 2 y 1 y 2 4 × 3(x1,y1),(x2,y2)x1x2y1y24×3

insira a descrição da imagem aqui

Agora podemos simular as arestas do gráfico original usando pares de pontos na parte inferior ou à direita, cada par em uma linha separada ou em uma coluna separada; veja a figura a seguir para dois nós adjacentes vinculados horizontalmente (em uma nova linha inferior, dois pontos são adicionados um na mesma coluna do ponto de interface do primeiro gadget e o outro na mesma coluna do ponto de interface do segundo gadget).WEW

insira a descrição da imagem aqui

Em todos os gadgets, pode haver no máximo pontos de canto (1 gerado pelo ponto de interface de entrada, 1 gerado pelo ponto de interface de saída, 2 gerado pelo turno extra em travessias retas e 2C no zig-zag interno), os pontos usado para as arestas pode gerar no máximo pontos de canto.2 e4+2C2e

Suponha-se que o gráfico original tem nodos e arestas, se escolher , e como o número de pontos de canto que deverá ser utilizada, então forçar o polígono "escondido" do quebra-cabeças para atravessar todos os gadgets; mas todos os gadgets podem ser inseridos / encerrados exatamente uma vez (por meio de um par de células de interface); portanto, o problema terá uma solução se e somente se o gráfico original tiver um caminho hamiltoniano.e C > ( 4 n + 2 e ) k = 2 C nneC>(4n+2e)k=2Cn

Marzio De Biasi
fonte
5

Não é uma resposta, apenas algumas referências. Primeiro, escrevi um artigo (há muito tempo!) Sobre o caso em que todos os pontos do conjunto devem ser um canto poligonal. Nesse caso, não é de surpreender que exista (no máximo) um polígono e é fácil encontrar: "Exclusividade da conexão ortogonal dos pontos", em Morphology computacional , ed. GT Toussaint, Elsevier, Holanda do Norte, 1988, 97-104.V

Segundo, há uma bela atualização deste trabalho de Maarten Löffler e Elena Mumford, em um artigo " Gráficos retilíneos conectados em conjuntos de pontos ", Journal of Computational Geometry , 2 (1), 1–15, 2011. De seu resumo:

V

Joseph O'Rourke
fonte