Saya tertarik pada masalah pengemasan salinan identik persegi panjang (2 dimensi) menjadi cembung (2 dimensi) poligon tanpa tumpang tindih. Dalam masalah saya, Anda tidak diperbolehkan memutar persegi panjang dan dapat mengasumsikan bahwa mereka berorientasi paralel dengan sumbu. Anda hanya diberi dimensi persegi panjang dan simpul poligon dan ditanya berapa banyak salinan identik persegi panjang yang bisa dimasukkan ke dalam poligon. Jika Anda diizinkan untuk memutar persegi panjang masalah ini dikenal sebagai NP-keras saya percaya. Namun, apa yang diketahui jika Anda tidak bisa? Bagaimana jika cembung poligon hanyalah segitiga? Adakah algoritma perkiraan yang diketahui jika masalahnya memang NP-hard?
Ringkasan sejauh ini (21 Maret '11). Peter Shor mengamati bahwa kita dapat menganggap masalah ini sebagai salah satu kotak unit pengemasan dalam poligon cembung dan bahwa masalah tersebut ada di NP jika Anda memaksakan ikatan polinom pada jumlah kotak / persegi panjang yang akan dikemas. Sariel Har-Peled menunjukkan ada PTAS untuk kasus terikat polinomi yang sama. Namun, secara umum jumlah kotak yang dikemas dapat eksponensial dalam ukuran input yang hanya terdiri dari daftar pendek pasangan bilangan bulat. Pertanyaan-pertanyaan berikut tampaknya terbuka.
Apakah versi lengkap tidak terikat di NP? Apakah ada PTAS untuk versi tanpa batas? Apakah kasus yang dibatasi secara polinomi dalam P atau NPC? Dan favorit pribadi saya, apakah masalahnya lebih mudah jika Anda hanya membatasi diri untuk mengemas kotak unit menjadi segitiga?
Jawaban:
Masalahnya dapat diformulasi ulang sebagai memilih jumlah maksimum poin di dalam poligon cembung, sehingga setiap pasangan dari mereka berada dalam jarak (di bawah metrik) setidaknya 1 dari satu sama lain (hanya memikirkan pusat-pusat kuadrat) . Ini pada gilirannya terkait dengan masalah yang sama di mana seseorang menggunakan jarak Euclidean biasa. Hal ini pada gilirannya terkait dengan penyambungan, di mana seseorang tertarik untuk memecah poligon menjadi daerah yang berperilaku baik (yaitu, Anda mengambil diagram Voronoi dari pusat [lihat tessellations Centonoal Voronoi]).L.∞ 1
Lagi pula, -approximation cukup mudah. Anda secara acak menggeser kisi sidelength O ( 1 / ϵ ) . Jepitkan poligon ke dalam kisi-kisi, dan pecahkan masalah di dalam setiap irisan poligon dengan kisi-kisi menggunakan kekuatan kasar. Algoritma dengan waktu berjalan O ( M ∗ n o i s e ( ϵ ) ) harus mudah diikuti, di mana M adalah jumlah titik (yaitu, persegi panjang), dan n o i s e ( ϵ )( 1 - ϵ ) O ( 1 / ϵ ) O ( M∗ n o i s e ( ϵ ) ) M. n o i s e ( ϵ ) adalah beberapa fungsi menghebohkan yang hanya bergantung pada .ϵ
sumber
Dua makalah ini membahas masalah Anda:
EG Birgin dan RD Lobato, " pengemasan Orthogonal dari persegi panjang identik dalam daerah cembung isotropik ", Komputer & Teknik Industri 59, hal. 595-602, 2010.
EG Birgin, JM Martínez, FH Nishihara dan DP Ronconi, " Pengemasan orthogonal dari barang-barang persegi panjang di dalam daerah cembung acak dengan optimasi nonlinear ", Computers & Operations Research 33, hlm. 3535-3548, 2006.
sumber
Peter Shor mengamati bahwa dengan men-rescaling, masalah ini menjadi tentang pengemasan kotak kuadrat menjadi poligon cembung.
Sunting: sisa jawaban ini tidak berlaku, karena menjatuhkan persyaratan yang dinyatakan secara eksplisit bahwa bentuk yang akan dikemas semuanya berukuran sama.
Pertanyaan terkait NP-Hardness dari kasus khusus masalah pengemasan orthogonal menyebutkan sebuah makalah dengan hasil yang diperlukan untuk pertanyaan pertama:
Dari kertas:
Karenanya masalahnya adalah NP-hard bahkan untuk kasus khusus di mana persegi panjang yang akan dikemas mirip dengan wadah. (Berbeda dengan penulis makalah ini, saya tidak sepenuhnya yakin bahwa masalahnya ada di NP, karena posisi mungkin harus ditentukan untuk sejumlah besar presisi, yang dapat menyebabkan verifikasi tidak lagi polinomial dalam ukuran input. )
sumber
Mungkin makalah ini dapat menarik bagi Anda:
Memasang poligon dengan persegi panjang oleh Kenyon & Kenyon di FOCS 92.
sumber
Jika poligon yang ingin Anda kemas belum tentu cembung, maka saya pikir masalahnya menjadi NP-hard. Ini bukti yang sangat samar. Pengurangan ini dari beberapa jenis masalah Planar-3-SAT. Untuk setiap variabel Anda dapat memiliki tempat 1,1 x 1, tergantung di mana di area ini Anda menempatkan satu kotak akan menentukan apakah variabel Anda benar salah. Juga, jika Anda meninggalkan 0,1 area kiri / kanan, maka Anda dapat memindahkan dua kotak lainnya sedikit lebih dalam, dan juga yang di belakang mereka, akhirnya memberikan 0,1 ruang kosong lain di tempat lain yang bersama-sama sekarang mempengaruhi empat kotak dan seterusnya. Setelah Anda memiliki salinan sebanyak kejadian literal masing-masing, Anda menghubungkan tabung ini ke masing-masing komponen klausa dan di sana lagi menggunakan beberapa gadget yang sama untuk memastikan bahwa dari tiga tabung ingoing setidaknya satu harus memiliki ruang ekstra .1
sumber