Himpunan bagian maksimal dari himpunan titik yang muat dalam disk unit
Misalkan ada satu set $P$ dari $n$ menunjuk ke pesawat, dan biarkan $P_1, \dots, P_k$ menjadi himpunan bagian yang berbeda dari $P$ sedemikian rupa sehingga semua mengarah $P_i$ muat di dalam satu unit disk untuk semua $i$, $1\le i\le k$.
Apalagi masing-masing $P_i$ adalah maksimal, yaitu, tidak ada disk unit yang dapat menutupi subset dari $P$ itu adalah superset ketat dari $P_i$. Secara visual, jika kita memindahkan unit disk yang menutupi$P_i$ untuk menutupi poin yang tidak masuk $P_i$, maka setidaknya satu titik yang ada di dalam disk tersebut akan terungkap.
Berikut ini contohnya:

Pada gambar di atas, ada tiga himpunan bagian maksimal.
Saya tidak tahu apakah masalah ini memiliki nama atau telah dipelajari sebelumnya, tetapi inilah pertanyaan saya.
- Bisa $k$ menjadi eksponensial sehubungan dengan $n$?
- Jika tidak, maka kita dapat menemukan himpunan bagian maksimal tersebut dalam waktu polinomial wrt $n$?
Saya pikir ada banyak subset seperti itu secara eksponensial karena argumen berikut:
Misalkan titik adalah pusat dari beberapa disk dengan jari-jari$1/2$. Jika bagian dari titik-titik tersebut masuk ke dalam disk unit, maka mereka membentuk sebuah klik. Karena ada banyak klik secara eksponensial dalam satu set disk, maka harus ada banyak himpunan bagian maksimal secara eksponensial dari kumpulan titik khusus ini yang sesuai dengan disk unit.
Jawaban
Mari kita definisikan sebuah fungsi $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, mengembalikan sejumlah poin dari set $P$, ditutupi oleh disk unit dengan bagian tengah di titiknya $(x, y)$. Ini adalah fungsi konstan sebagian, dan mudah untuk melihat bahwa domainnya dapat dianggap sebagai subdivisi planar, yang ditentukan oleh semua persimpangan disk unit, berpusat pada titik-titik dari himpunan$P$. Pembagian ini berisi simpul - simpul (= titik-titik perpotongan), tepi-tepi (= busur-busur melingkar) dan muka - muka (= potongan-potongan bidang, dimana fungsinya$f$mengembalikan nilai yang sama). Kami akan mengatakan bahwa wajah-wajah ini diberi label oleh nilai ini.
Kami akan berasumsi bahwa grafik planar, yang ditentukan oleh subdivisi ini, adalah grafik beraturan 4 - ini adalah asumsi umum, yang berarti bahwa semua titik di $P$berada pada posisi umum (setiap titik perpotongan dimiliki tepat oleh dua lingkaran). Contoh subdivisi tersebut untuk$n=3$ di bawah, di mana label untuk setiap wajah (termasuk yang eksternal) ditunjukkan dengan warna merah.

Sejauh yang saya mengerti himpunan bagian maksimal Anda $P_i$dapat dikaitkan dengan permukaan seperti itu dari subdivisi ini, yang memiliki label lebih besar dari semua label pada permukaan tetangganya . Ini semacam interpretasi statis dari semantik "disk bergerak" Anda, yang Anda gunakan dalam definisi subset maksimal.
Subdivisi akan berisi wajah sebanyak mungkin jika semua lingkaran unit saling berpasangan. Dapat ditunjukkan, bahwa dalam hal ini:
- jumlah simpul adalah $n(n-1)$
- jumlah tepi adalah $2n(n-1)$
- jumlah wajah adalah $n(n-1)+2$
Jadi, jawaban atas pertanyaan Anda adalah:
- Tidak, nomornya $k$ dari himpunan bagian maksimal adalah $O(n^2)$, karena tidak boleh lebih dari jumlah semua wajah.
- Ya, semua himpunan bagian maksimal dapat ditemukan di $O(n^3)$ waktu dengan algoritma pemindaian naif.
Adapun nama masalah ini - sepertinya itu terkait dengan beberapa variasi masalah Unit Disk Cover.