Diberikan poligon ortogonal (poligon yang sisi-sisinya sejajar dengan sumbu), saya ingin menemukan set terkecil dari kotak-kotak yang terpisah-pisah, yang persatuannya sama dengan poligon.

Saya menemukan beberapa referensi untuk masalah yang sedikit berbeda, seperti:

• Menutupi poligon ortogonal dengan kotak - mirip dengan masalah saya, tetapi kotak yang menutupinya memungkinkan untuk tumpang tindih. Masalah ini memiliki solusi polinomial ( Aupperle, Conn, Keil dan O'Rourke, 1988 ; Bar-Yehuda dan Ben-Hanoch, 1996 ).
• Ubin / dekomposisi / partisi poligon ortogonal menjadi persegi panjang . Masalah ini memiliki solusi polinomial ( Keil, 2000 ; Eppstein, 2009 ).
• Menutupi poligon ortogonal dengan persegi panjang - masalah ini dikenal sebagai NP-lengkap ( Culberson dan Reckhow, 1988 ).

Saya mencari algoritma untuk ubin minimal dengan kotak .

Saya akan mencoba menunjukkan masalah ini NP-hard, dengan pengurangan dari .$\text{Planar-}3\text{-SAT}$

Pengurangan dari$\text{Planar-}3\text{-SAT}$

Beberapa Gadget dasar

Gadget adalah konfigurasi internal geometri yang memungkinkan kita membuat gerbang untuk digunakan dalam suatu rangkaian, yang akan kita kurangi .$\text{Planar-}3\text{-SAT}$

4X3-gadget

Gadget ini memiliki dua status minimal-kuadrat-partisi yang valid :

^{Kiri A 4x3-gadget . Tengah dan kanan: Dua kemungkinan status partisi-kuadrat minimum .}

5X4-gadget

Gadget ini, persis seperti gadget 4X3 , hanya dengan dimensi lebih besar.

^{Meninggalkan A 5X4-gadget . Tengah dan kanan: Dua kemungkinan status partisi-kuadrat minimum .}

gadget titik akhir

Sebuah titik akhir-gadget adalah sebuah 5x4-gadget . Ini sering digunakan sebagai titik akhir / pin gerbang . Salah satu dari dua status titik akhir dapat dinilai sebagai benar, dan yang lainnya salah. Endpoint tanda kedua ujung, satu sebagai dan yang lain sebagai . Akhir yang ditutupi oleh kotak besar adalah nilai titik akhir.$T$$F$

^{Kiri: Bingkai rangka akhir-gadget . Pusat: Titik akhir bernilai sejati. Kanan: Titik akhir bernilai salah.}

gadget i-wire

Sebuah gadget i-kawat adalah singkatan kawat implikasi .

Aturan:

• Sebuah gadget i-kawat terdiri dari persegi panjang aneh-panjang panjang lebih dari dan lebar .$2$$2$
• Sebuah gadget i-kawat dapat memiliki minimal persegi partisi-negara , mendorong dari satu sisi, yang lain, atau tidak; sebuah i-kawat di negara bagian ketiga ini akan disebut secara lokal unconstrainted .$3$

Contoh:

^{Gambar 7: Sebuah i-kawat gadget panjang , dan lebar .$7$$2$}

Inilah cara penggunaannya:

^{Gambar 8,9 , Kiri: bingkai gambar i-wire melintasi dua titik akhir . Kanan: Serikat.}

Sekarang, jika satu titik akhir berada dalam kondisi yang tepat, itu memaksa titik akhir lainnya ke posisi terdorong. Contoh:

^{Kiri: Diagram partisi kotak; saklar kiri turun, "mendorong" semua kotak ke bawah i-wire dan akhirnya, menekan saklar lainnya ( titik akhir ). Kanan: Diagram partisi kotak; titik akhir kiri penuh, "mendorong" semua kotak ke bawah i-wire , dan memaksa titik akhir di kiri untuk "naik".}

Ini pada dasarnya adalah implikasi logis. Pertimbangkan "down" untuk menjadi kenyataan, maka kita memiliki . Kita juga dapat melakukan dengan hanya membalik titik akhir di sebelah kanan.$A \implies \neg B$$A \implies B$

Namun, ini meninggalkan kasus yang tidak dibatasi:

Jika kita menggabungkan dua kabel-i , kita bisa mendapatkan implikasi dua arah, pada dasarnya persamaan (dalam) boolean:

Jadi, dua kabel i dapat membawa hubungan kesetaraan penuh, seperti sirkuit - pada kenyataannya, itu adalah sirkuit. Kami akan menggunakan pasangan ini untuk membangun kawat yang dapat digunakan .

Setiap gadget i-wire berkontribusi kotak-partisi ke partisi-persegi- minimum , simpan untuk sudut-berbagi dengan gadget lain.$\frac{l-1}{2}+2$

i-wires dapat diorientasikan sesuai kebutuhan.

kawat

Sebuah kawat terdiri dari sepasang i-wires yang terhubung ke gerbang yang sama di setiap titik akhir.

• The i-kabel yang berwarna merah dan hijau.
• Pasangan harus dipisahkan oleh spasi (konvensi).$3$
• Setiap pin gerbang akan memiliki kontak hijau dan merah; sebuah kawat harus terhubung dengan benar.
• Aturan invarian: satu i-wire didorong ke arah yang berlawanan dari i-wire lainnya , masing-masing gerbang mengasumsikan ini, dan memastikan hal ini (kecuali dinyatakan sebaliknya).
• Karena setiap kawat berisi implikasi dua arah, ia membawa nilai-nilai dari gerbang ke gerbang seperti kabel di sirkuit.
• Setiap kabel harus terhubung ke gerbang di kedua ujungnya. . Gagal ini dapat merusak asumsi beberapa gerbang yang saya jelaskan, dan aturan invarian di atas; Namun, gerbang yang memiliki titik akhir melintasi timah aman - Anda dapat menghubungkan kabel liar ke titik akhir ini tanpa khawatir akan merusak gerbang.
• kabel harus panjangnya aneh, termasuk kabel ke sirkuit apa pun yang dihubungkannya; namun saya akan menjelaskan gerbang ganjil di bawah yang memungkinkan kawat genap menjadi ganjil.

Gambar :

^{Atas: Sebuah kawat .}

^{Kiri dan kanan: Dua kemungkinan minimal persegi partisi-negara dari kawat . Perhatikan bahwa jika kawat hanya sepanjang ini, ia tidak akan bisa bergeser ke kanan atau kiri, dan harus memecah satu kotak menjadi potongan-potongan yang lebih kecil.}

kabel dapat diorientasikan sesuai kebutuhan.

bend-gate : Membungkuk kawat

^{Kiri: Tampilan kawat-bingkai. Kanan: Tampilan gabungan.}

Perhatikan penggunaan gadget 4X3 . Ini digunakan untuk memperbaiki ujung merah ke panjang aneh.

Berikut ini adalah dua kemungkinan kondisi lengkung minimal persegi :

^{Kiri dan kanan: Dua kemungkinan status partisi lentur persegi-persegi-persegi-minimum .}

Gerbang dapat berorientasi sesuai kebutuhan. Jelas, gerbang ini dapat dicerminkan untuk bekerja ke arah lain.

Miringkan kawat

Mudah untuk memindahkan kawat. Ilustrasi wireframe:

gerbang bernama-nilai

Sebuah gerbang bernama-nilai pada dasarnya adalah titik akhir sebagai gerbang dengan satu kontak kawat:

odd-skip-gate : Aneh melewatkan kawat

Terkadang tidak nyaman untuk hanya memiliki kabel panjang ganjil. Sebagai contoh:

Seperti yang Anda lihat, sedikit ekstensi itu sedikit mengganggu. Berikut adalah solusi yang sesuai, menggunakan gerbang 4X3 :

Jadi, mengubah ini menjadi gerbang, kita mendapatkan odd-skip-gate (dalam rangka gambar):

Gerbang dapat berorientasi sesuai kebutuhan.

twist-gate : Memutar kawat

Kadang-kadang Anda mendapatkan kabel-i merah dan hitam di sisi yang salah untuk digunakan dengan gerbang . Dalam hal ini, disediakan twist-gate , untuk memutar kabel-i merah dan hitam ke sisi yang berlawanan.

Ilustrasi wireframe:

Yakinkan diri Anda bahwa itu berfungsi:

^{Mulai dari , ikuti panah-tekan, semuanya harus dipaksa dan konsisten.$A$}

Gerbang dapat berorientasi sesuai kebutuhan.

split-gate : Memisahkan kawat

Memisahkan kawat, bingkai foto:

Yakinkan diri Anda bahwa itu bekerja:

^{Gambar: Mulai dari , ikuti panah-tekan. Semuanya harus dipaksakan dan konsisten.$A$}

^{Gambar: Mulai dari , ikuti panah-tekan. Semuanya harus dipaksakan dan konsisten.$A$}

Catatan: Setiap kabel yang masuk dan keluar dari splitter benar-benar harus terhubung ke titik akhir di suatu tempat, untuk mempertahankan invarian. Atau, Anda dapat menambahkan titik akhir ke masing-masing pasangan lead splitter.

Gerbang dapat berorientasi sesuai kebutuhan.

bukan gerbang

Gerbang tidak mengambil kawat dan menghasilkan kawat yang memiliki implikasi sebaliknya. Ini pada dasarnya adalah twist-gate , kecuali bahwa itu melabel ulang warna kabel. The tidak-gerbang terlihat seperti ini:

Dan pandangan dari dua kemungkinan kondisi:

Gerbang dapat berorientasi sesuai kebutuhan.

gerbang klausa

Untuk gerbang klausa , pertama-tama kami perkenalkan gadget klausa :

^{Kiri ke kanan: 1 klausa-gadget . 2-4: yang berbeda minimal persegi partisi-negara . $3$}

Seperti inilah bentuk gerbang:

Kami dapat menunjukkan berbagai kondisi gerbang ini (penjelasan di bawah semua ilustrasi):$3$

Penjelasan:

2. Mulai dari gadget-klausa dan ikuti panah.
3. Non-panah-garis berarti bahwa itu adalah bagian dari suatu rangkaian, tetapi tidak dipaksa ke keadaan oleh gerbang.
4. Keadaan gadget-klausa memaksa salah satu titik akhir untuk dinilai benar .

Seperti yang Anda lihat, setidaknya salah satu input harus dinilai benar . Inilah yang dibutuhkan oleh klausa .$3\text{-CNF}$

Gerbang dapat berorientasi sesuai kebutuhan.

Pengurangan

Biarkan menjadi rumus , di manaPlanar- 3 $\Phi(\mathbf x)$$\text{Planar-}3\text{-SAT}$

Bantuan visual (sumber asli: Terrain Guarding is NP-Hard (PDF) , direproduksi dalam tikz):

Kemudian:

1. Untuk setiap variabel , tempatkan dua gerbang variabel bernama di sebelah satu sama lain, beri nama salah satunya dan yang lain .x i ¬ x $x_i\in\mathbf x$$x_i$$\neg x_i$
2. Hubungkan gerbang satu sama lain dengan tidak-gerbang , sehingga mereka secara logis meniadakan nilai masing-masing.
3. Tempatkan variabel 'gerbang' poligon di lokasi mereka di planar-embedding.
4. Untuk setiap klausa, letakkan gerbang klausa di lokasi klausa dalam penyisipan planar.
5. Menggunakan gerbang yang dijelaskan di atas, hubungkan semua variabel ke klausa mereka.
6. Jalankan algoritma-minimum-kuadrat-partisi pada hasil yang dihasilkan dari semua poligon gerbang (seluruh rangkaian).
7. Jika algoritma mengembalikan jumlah dari semua ukuran minimum-kuadrat-partisi- gerbang (mengurangi untuk sudut-berbagi) maka itu memuaskan. Jika tidak memuaskan, itu akan memaksa gadget terbatas untuk memecah menjadi kotak yang lebih kecil, sehingga meningkatkan jumlah kotak yang diperlukan untuk mempartisi rangkaian.

Mengapa ini berhasil?

• Setiap gadget memiliki ukuran keadaan partisi-kuadrat minimal ; yaitu, partisi minimum persegi dari gadget itu adalah ukuran tertentu.
• Beberapa gadget memiliki beberapa status dengan ukuran ini; masing-masing negara ini adalah partisi minimum-kuadrat yang valid .
• Ketika gadget digabungkan hanya di sudut-sudutnya, jumlah kondisi partisi minimum kuadrat gadget adalah * masih status partisi-minimum-kuadrat-persegi penyatuannya; Anda dapat melihat ini secara intuitif: bergabung di sudut tidak memberikan ruang yang cukup bagi kotak untuk berkembang / terhubung dengan kotak dari gadget lain.
• Meskipun menggabungkan gadget di sudut tidak mengurangi ukuran total partisi-kuadrat minimum , hal itu terkait dan membatasi gadget satu sama lain.
• Dengan gerbang yang ditunjukkan di atas, Anda dapat membatasi keadaan, sehingga jika rumus logis tidak memuaskan, maka satu atau lebih gadet harus masuk ke kotak yang lebih kecil, dan menambah ukuran partisi minimum kuadrat .

sumber grafik

• squaretilings1.tex ( writelatex )
• squaretilings2.tex ( writelatex )
• clausegate.tex ( writelatex )

Anda juga dapat melihat gambar yang lebih besar dengan menghapus sufiks "s", "m", "l", url imgur. Misalnya, Anda dapat melihat gambar yang lebih besar dari ini: http://i.stack.imgur.com/6CKlGs.jpg dengan membuka http://i.stack.imgur.com/6CKlG.jpg . Perhatikan "s" yang hilang sebelum .jpg.

Makalah lama yang saya tulis bersama menetapkan bahwa masalah penutupnya adalah polinomial untuk poligon tanpa lubang, dan NP-lengkap dengan lubang. Kami menunjukkan bahwa grafik yang mendasarinya adalah chordal. Harap dicatat: algoritma ini polinomial dalam jumlah dari kuadrat unit dalam poligon, .O ( N 3 / 2$N$$O(N^{3/2})$

"Menutupi poligon ortogonal dengan kotak." LJ Aupperle dan HE Conn dan JM Keil dan Joseph O'Rourke. Proc 26 Allerton Conf. Komunal. Kontrol Komputasi. , hal. 97-106, 1988. ( tautan untuk mengunduh pemindaian PDF )

Namun, penutup yang dihasilkan mungkin termasuk kotak yang tumpang tindih. Anda mencari ubin, di mana kotak tidak diizinkan tumpang tindih, jadi masalah Anda tidak persis sama.