Varian galeri seni dengan visibilitas berpasangan?

Masalah galeri seni tradisional membuat suatu daerah dan penjaga dengan beberapa pandangan tentang visibilitas, dan meminta jumlah penjaga minimum yang perlu ditempatkan untuk melihat seluruh wilayah.

Adakah yang pernah melihat varian galeri seni di mana wilayah visibilitas ditentukan oleh sepasang penjaga. Misalnya, satu formulasi mungkin bahwa suatu titik tertutup jika ada sepasang penjaga yang disk pembatas minimumnya mencakupnya?

reference-request cg.comp-geom Suresh Venkat
sumber

Quis custodiet ipsos custodes?

Artem Kaznatcheev

Nah, untuk menjawab pertanyaan @ Artem, ada gagasan penjaga yang terhubung , yang memiliki dua varian. Biarkan grafik visibilitas didefinisikan dengan sebuah simpul untuk masing-masing penjaga, dan tepi antara dua simpul jika penjaga dapat saling melihat. Jika grafik visibilitas terhubung, semua penjaga dijaga (kadang-kadang disebut "set penjaga yang dijaga"). Kondisi yang lebih kuat adalah bahwa grafik visibilitas memiliki komponen yang terhubung tunggal. Maka Anda memiliki satu set penjaga yang terhubung. Dan ya, ada cukup banyak pekerjaan di sini. Saya bahkan telah membuat blog tentang satu kertas.

Aaron Sterling

Aduh, di atas harus membaca "jika grafik visibilitas tidak memiliki simpul terisolasi, semua penjaga dijaga ..."

Aaron Sterling

"siapa yang menjaga para penjaga"? latin saya hanya babi :)

Suresh Venkat

Perhatikan bahwa dalam formulasi saya, saya tidak mengharuskan grafik visibilitas yang diinduksi terhubung. Meskipun ini mungkin bukan masalah dengan persegi panjang sumbu-paralel, itu sebenarnya mungkin masalah dengan daerah yang tidak begitu baik (seperti daerah elips). Tapi pointer penjaga yang terhubung adalah yang baik: Saya pikir mungkin beberapa varian masalah saya dapat diatasi dengan cara itu.

Suresh Venkat

Jawaban:

Saya tidak mengetahui adanya pekerjaan seperti itu. Namun, saya berharap bahwa masalah seperti itu akan menjadi NP-lengkap dan, untuk poligon berlubang, akan sulit diperkirakan seperti Set Cover. Masalah guard vertex / vertex yang relatif mudah, di mana penjaga hanya bisa berbaring pada verteks dan hanya verteks yang perlu dijaga, ini sulit ( Eidenbenz, Stamm, dan Widmayer (2001) ).

Untuk poligon sederhana, saya berharap masalah seperti itu adalah:

NP-lengkap
Keras-APX
Diperkirakan dalam faktor , di mana opt adalah jumlah penjaga yang optimal. $O(\log(\rm{opt}))$

Masalah vertex / vertex guarding adalah APX-hard untuk poligon sederhana ( Eidenbenz (1998) ).

Algoritma terbaik untuk masalah galeri seni untuk poligon sederhana didasarkan pada membangun jaring kecil. Dalam poligon sederhana, ruang rentang yang disebabkan oleh visibilitas poligon memiliki dimensi VC konstan. Lingkaran juga demikian. Oleh karena itu ruang rentang yang disebabkan oleh visibilitas poligon dalam poligon sederhana, lingkaran, dan persimpangan dan persatuannya, juga akan memiliki dimensi VC yang konstan dan Anda bisa mendapatkan algoritma -approximation. $\varepsilon$ $O(\log(\rm{opt}))$

Saya memikirkan masalah ini sedikit untuk tesis saya, tetapi sampai pada pendapat bahwa tidak ada varian yang sangat menarik yang tampaknya tidak mengurangi cukup dekat ke masalah yang diketahui melibatkan penjagaan tunggal.

James King
sumber

Agak terlambat untuk pertanyaan ini (maaf!). Setidaknya ada sedikit pekerjaan.

(1) Ini tampaknya menjadi makalah penelitian sarjana (Swarthmore): "Cakupan Ganda Optimal di Galeri Seni," Scott Dalane, Andrew Frampton, 2008, tautan PDF . Dari kesimpulan mereka:

$\lfloor 2n/3 \rfloor$ $n^2$

$\lfloor 2n/3 \rfloor$

Joseph O'Rourke
sumber

Jadi saya sudah memikirkan hal ini. Saya pikir perbedaan utama antara cakupan ganda dan masalah saya adalah bahwa ada masalah "keterhubungan" ini. Dengan kata lain, tak satu pun wilayah visibilitas dari kedua penjaga itu diaktifkan kecuali mereka "terlihat" satu sama lain. Sangat mudah untuk membangun contoh di mana Anda dapat menggandakan wilayah dengan penjaga yang tidak saling bertemu. Sekarang masalah penjaga yang terhubung juga telah dilihat, tetapi dalam konteks berbeda yang sekali lagi tidak berlaku di sini - khususnya di sana Anda mengharuskan grafik visibilitas penjaga terhubung, dan saya tidak membutuhkannya.

Suresh Venkat

p

$p$

p

$p$

p

$p$

Tidak terlalu. itu bukan visibilitas murni. Sepasang penjaga mendefinisikan "wilayah visibilitas" dan sebuah titik tercakup jika terletak di wilayah visibilitas penjaga. Faktanya adalah mungkin bagi penjaga yang tidak dapat melihat satu sama lain ATAU titik dalam pengertian "garis pandang" tradisional untuk "menutupi" intinya.

Suresh Venkat

Terima kasih telah mengklarifikasi. Model ini memang terlihat berbeda dari yang saya tahu.

Joseph O'Rourke