Kompleksitas puzzle poligon tersembunyi di kotak persegi?

Hiroimono adalah puzzle lengkap populer . Saya tertarik pada kompleksitas komputasi dari teka-teki terkait.$NP$

Masalahnya adalah:

Input : Diberikan satu set titik pada pada x kotak persegi dan integer$n$$n$$k$

Pertanyaan : Apakah ada poligon bujursangkar (sisi-sisinya sejajar dengan atau sumbu) sedemikian sehingga jumlah titik pada sudut poligon setidaknya ?$x$$y$$k$

Setiap sudut poligon harus berada di salah satu titik input (sehingga tikungan hanya diperbolehkan pada titik input).

Apa kompleksitas masalah ini? Apa kompleksitasnya jika solusinya terbatas pada poligon bujursangkar cembung?

EDIT 13 April: Formulasi alternatif: Temukan poligon bujursangkar dengan sudut maksimum pada titik yang diberikan.

Saya memikirkan pengurangan aneh ini (kemungkinan salah besar :-). Ide: reduksi dari jalur Hamilton pada grafik kisi dengan derajat ; setiap node dari grafik planar dapat digeser sedemikian rupa sehingga setiap "baris" ( nilai ) dan setiap "kolom" ( nilai ) mengandung paling banyak satu simpul. Grafik dapat diskalakan dan setiap node dapat diganti dengan gadget persegi dengan banyak titik; tautan horizontal antara gadget (tepi grafik asli) dibuat menggunakan pasangan titik pada baris berbeda, tautan vertikal menggunakan pasangan titik pada kolom berbeda. Node traversals dipaksa menggunakan "banyak titik" dari gadget kotak.$\leq 3$$y$$x$

Gadget simpul direpresentasikan dalam gambar berikut:

Ini memiliki 3 "titik antarmuka" (pada kolom / baris yang berbeda), dan perbatasan bagian dalam titikPolyline yang melintasi gadget dari satu titik antarmuka ke titik yang lain dapat memiliki sejumlah sudut yang sebanding dengan (tiga lintasan gadget ditampilkan pada gambar), khususnya jumlah titik sudut antara dan (jumlah total poin gadget adalah ). Gadget dapat diputar untuk mendapatkan kombinasi titik antarmuka lainnya ( , , ).$[W,N,E]$$C \times C$$C$$2C$$2C+2$$C \times C - 4 + 6$$[N,E,S]$$[E,S,W]$$[S,W,N]$

Sekarang kita dapat menggeser grafik grid planar sedemikian rupa sehingga untuk setiap pasangan node , dan . Lihat gambar kisi sederhana berikut ini . Selanjutnya, kita dapat mengatur skala grafik dan mengganti setiap node dengan gadget di atas. Pada tahap ini setiap gadget "terisolasi": polyline tidak dapat berpindah dari satu gadget ke gadget lainnya.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$

Sekarang kita dapat mensimulasikan tepi grafik asli menggunakan pasangan titik di bagian bawah atau di sebelah kanan, masing-masing pasangan di baris terpisah atau di kolom terpisah; lihat gambar berikut untuk dua node yang berdekatan yang terhubung secara horizontal (di baris bawah baru dua titik ditambahkan satu pada kolom yang sama dari titik antarmuka dari gadget pertama, yang lain pada kolom yang sama dari titik antarmuka dari gadget kedua).$E$$W$

Pada setiap gadget dapat ada maks titik sudut (1 dihasilkan oleh titik antarmuka masuk, 1 dihasilkan oleh titik antarmuka keluar, 2 dihasilkan oleh ekstra turn pada lintasan lurus dan 2C pada zig-zag bagian dalam), poin digunakan untuk tepi dapat menghasilkan maksimal poin sudut.2 $4 + 2C$$2e$

Misalkan grafik asli memiliki simpul dan tepi , jika kita memilih , dan sebagai jumlah titik sudut yang harus digunakan, maka kita memaksakan "tersembunyi" poligon teka-teki untuk lintasi setiap gadget; tetapi setiap gadget dapat dimasukkan / keluar tepat sekali (melalui sepasang sel antarmuka); jadi masalahnya ada solusi jika dan hanya jika grafik grid asli memiliki jalur Hamilton.e C > ( 4 n + 2 e ) k = 2 C $n$$e$$C > (4n+2e)$$k = 2Cn$

Bukan jawaban, hanya beberapa referensi. Pertama, saya menulis makalah (dulu!) Pada kasus di mana setiap titik dalam himpunan harus merupakan sudut poligon. Dalam hal ini, tidak mengherankan bahwa ada (paling banyak) satu poligon, dan mudah ditemukan: "Keunikan Orthogonal Connect-the-Dots," dalam Computational Morphology , Ed. GT Toussaint, Elsevier, Belanda Utara, 1988, 97-104.$V$

Kedua, ada pembaruan yang indah untuk karya ini oleh Maarten Löffler dan Elena Mumford, dalam sebuah makalah, " Grafik Rectilinear Terkoneksi pada Point Sets ," Journal of Computational Geometry , 2 (1), 1-15, 2011. Dari Abstrak mereka:

Kami mempelajari pertanyaan apakah ada orientasi sedemikian rupa sehingga adalah himpunan simpul dari grafik bujursangkar yang terhubung dalam orientasi itu. ... Kami membuktikan bahwa paling banyak satu orientasi seperti itu dapat dimungkinkan, hingga rotasi sepele 90 derajat di sekitar beberapa sumbu.$V$