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

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 $n$$n$$k$

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 $x$$y$$k$

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.

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 $\leq 3$$y$$x$

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

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 \times C$$C$$2C$$2C+2$$C \times C - 4 + 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 1 ≠ x 2 y 1 ≠ y 2 4 × $(x_1,y_1), (x_2,y_2)$$x_1 \neq x_2$$y1 \neq y_2$$4 \times 3$

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).$E$$W$

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 $4 + 2C$$2e$

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 $n$$e$$C > (4n+2e)$$k = 2Cn$

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$