Menutupi poligon sederhana dengan lingkaran

10

Misalkan saya memiliki poligon sederhana dan bilangan bulat k . Apa saja pendekatan yang ada untuk menemukan jari-jari terkecil r sehingga saya bisa menutup S dengan k lingkaran jari-jari r ? Bagaimana jika r diperbaiki, dan saya ingin meminimalkan k ?SkrSkrrk

cg.comp-geom planar-graphs set-cover pengguna771871
sumber

Jawaban:

11

Gunakan algoritma pengelompokan k-center: lihat Bagian 4.2 di http://goo.gl/pLiEO .

Orang bisa mendapatkan algoritma aproksimasi 1+ eps menggunakan sliding grids.

Wajar untuk menganggap masalahnya adalah NP-Hard karena pekerjaan oleh Feder dan Greene.

Sariel Har-Peled
sumber
1
Itulah yang diberikan oleh kisi-kisi geser ...
Sariel Har-Peled
Terima kasih atas jawaban Anda. Saya kurang lebih terbiasa dengan kisi-kisi geser. Dalam skenario titik-titik itu sangat bergantung pada kenyataan bahwa di setiap sel grid seseorang dapat menyelesaikan masalah penutup secara optimal karena setiap disk berisi dua titik pada batasnya, ditambah jumlah disk untuk menutup sel terikat. Dengan demikian seseorang dapat menyelesaikannya dengan kekerasan. Tetapi dalam pengaturan poligon, saya tidak melihat bagaimana menyelesaikan masalah dalam satu sel jaringan secara optimal. Maukah Anda memberikan beberapa petunjuk tentang ini?
101011
Kisi-kisi geser menyiratkan bahwa di dalam sel kisi ukuran solusi kecil. Maka Anda perlu memecahkan masalah di dalam setiap sel kotak (biasanya tepat) menggunakan beberapa algoritma lainnya. Berikut adalah cara alternatif untuk memikirkannya - sampel poligon sangat padat, dan kemudian selesaikan masalah Anda pada sampel ... Dan ya, detail pasti tentang cara melakukan ini mungkin sangat menyakitkan ... Jadi, anggap Anda memiliki poligon dengan n tepi, dan Anda tahu solusi optimal adalah ukuran k. Apakah Anda tahu cara menyelesaikan masalah persis dalam kasus ini?
Sariel Har-Peled
Terima kasih lagi. Setelah beberapa pemikiran lagi saya masih tidak tahu bagaimana cara menutup poligon secara optimal dengan k disk, bahkan jika saya tahu k. Fakta bahwa ada sedikit sifat diskrit yang membuatnya sangat sulit bagiku. Adapun pendekatan pengambilan sampel Anda: Setelah pengambilan sampel, apakah Anda ingin hanya mencakup bagian sampel? Bukankah kita kemudian mengalami masalah membuang banyak disk untuk mengisi kekosongan?
101011
1
N×NN=O(k/ϵ)ϵ