Złożoność ukrytej łamigłówki wielokątów na kwadratowych siatkach?

Hiroimono jest popularną łamigłówką . Interesuje mnie złożoność obliczeniowa powiązanej układanki.$NP$

Problemem jest:

Dane wejściowe : Biorąc pod uwagę zestaw punktów na siatce kwadratowej x i liczbie całkowitejn $n$$n$$k$

Pytanie : Czy istnieje wielokąt prostoliniowy (jego boki równoległe do osi lub ) taki, że liczba punktów na rogach wielokąta wynosi co najmniej ?y $x$$y$$k$

Każdy róg wielokąta musi znajdować się w jednym z punktów wejściowych (dlatego zagięcia są dozwolone tylko w punkcie wejściowym).

Jaka jest złożoność tego problemu? Jaka jest złożoność, jeśli rozwiązanie ogranicza się do wypukłych prostokątnych wielokątów?

EDYCJA 13 kwietnia: Alternatywne sformułowanie: Znajdź wielokąt prostoliniowy z maksymalnymi narożnikami w podanych punktach.

Myślałem o tej dziwnej redukcji (szanse, że to źle, są duże :-). Pomysł: redukcja ze ścieżki Hamiltona na wykresach siatkowych o stopniu ; każdy węzeł wykresu płaskiego można przesunąć w taki sposób, aby każdy „wiersz” ( wartość y ) i każda „kolumna” ( wartość x ) zawierała maksymalnie jeden węzeł. Wykres można skalować, a każdy węzeł można zastąpić kwadratowym gadżetem z wieloma punktami; poziome połączenia między gadżetami (krawędzie oryginalnego wykresu) są tworzone za pomocą par punktów w różnych rzędach, pionowe połączenia za pomocą pary punktów w różnych kolumnach. Przejścia węzłów są wymuszane przy użyciu „wielu punktów” kwadratowych gadżetów.$\leq 3$$y$$x$

Gadżet węzła jest przedstawiony na poniższym rysunku:

$[W,N,E]$$C \times C$$C$$2C$$2C+2$$C \times C - 4 + 6$$[N,E,S]$$[E,S,W]$$[S,W,N]$

$(x_1,y_1), (x_2,y_2)$$x_1 \neq x_2$$y1 \neq y_2$$4 \times 3$

$E$$W$

$4 + 2C$$2e$

$n$$e$$C > (4n+2e)$$k = 2Cn$

$V$

Po drugie, jest piękna aktualizacja tej pracy Maarten Löffler i Eleny Mumford, w artykule „ Connected Rectilinear Graphs on Point Sets ”, Journal of Computational Geometry , 2 (1), 1–15, 2011. Z ich streszczenia:

$V$