Masalah cakupan (pemancar dan penerima)

Saya mencoba menyelesaikan masalah cakupan berikut.

Ada pemancar dengan area jangkauan 1 km dan penerima. Putuskan dalam bahwa semua penerima dilindungi oleh pemancar apa pun. Semua pengirim dan pengirim diwakili oleh koordinat dan . $n$ $n$ $O(n\log n)$ $x$ $y$

Solusi paling maju yang bisa saya gunakan adalah . Untuk setiap penerima, urutkan semua pemancar berdasarkan jarak ke penerima saat ini, lalu bawa pemancar dengan jarak terpendek dan jarak terpendek ini harus dalam 0,5 km. $O(n^2\log n)$

Tetapi pendekatan naif terlihat jauh lebih baik dalam kompleksitas waktu . Hitung saja semua jarak antara semua pasangan pemancar dan penerima. $O(n^2)$

Saya tidak yakin apakah saya bisa menerapkan algoritma pencarian rentang dalam masalah ini. Sebagai contoh kd-tree memungkinkan kami untuk menemukan rentang seperti itu, namun saya tidak pernah melihat contohnya, dan saya tidak yakin apakah ada semacam range-search untuk lingkaran.

Kompleksitas yang diberikan mengasumsikan bahwa solusinya harus mirip dengan penyortiran. $O(n\log n)$

algorithms computational-geometry search-problem com
sumber

Jika diharapkan waktu

baik-baik saja, saya pikir Anda bisa membangun sebuah

tree atas pemancar (mengambil waktu

), dan kemudian melakukan query tetangga terdekat untuk masing-masing penerima (mengambil rata-rata dari

waktu untuk setiap penerima). Ini seharusnya untuk trik, tetapi saya menganggap Anda perlu kompleksitas kasus terburuk. Tampaknya ada beberapa trik untuk speedup ketika Anda melakukan beberapa terdekat query tetangga di

tree.

O (n \log n)

$O(n \log n)$

k d

$kd$

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

k d

$kd$

utdiscant

Saya kira algoritma garis sapu dapat melakukan trik: mengurutkan pemancar dan penerima dengan koordinat x dan melangkah melalui daftar. Manajemen pintar dari set pemancar yang layak sangat penting.

Raphael

@ Raphael, bisakah Anda menjelaskan sedikit lebih lanjut, sepertinya ini akan sangat lambat dalam kasus terburuk.

com

Saya pikir perlu melihat algoritma Fortune untuk menghitung diagram Voronoi di pesawat. Ia bekerja di

, dan diberi diagram Voronoi, masalah Anda menjadi mudah.

O (n \log n)

$O(n\log n)$

Syzygy

Jawaban:

Anda dapat menggunakan diagram Voronoi, bersama dengan struktur data Kirkpatrick untuk menyelesaikan masalah ini.

Seperti yang disarankan Raphael dan Syzygy, Anda dapat menggunakan algoritme Fortune (sweepline) untuk membuat diagram Voronoi. Waktu kasus terburuk: . $\mathcal{O}(n \log n)$

Diagram Voronoi akan memiliki banyak poligon, masing-masing berisi pemancar. Setiap titik dalam poligon paling dekat dengan pemancar itu. Jadi, jika Anda dapat mengetahui poligon mana yang berisi penerima, Anda dapat menemukan pemancar terdekat dengan entah bagaimana mencari tahu di mana poligon itu berada. Setelah itu, Anda memeriksa apakah pemancar itu berada dalam jarak . $1\ \text{km}$

Untuk menentukan poligon Voronoi mana yang berisi penerima, Anda terlebih dahulu melakukan triangulasi setiap poligon dalam diagram. Sekarang Anda memiliki mesh segitiga. Selanjutnya Anda menggunakan struktur data Kirkpatrick untuk menemukan segitiga yang mengandung titik tertentu dalam waktu , kasus terburuk. Membangun struktur data Kirkpatrick membutuhkan kasus terburuk. Setelah Anda tahu segitiga, Anda akan tahu poligon yang berisi itu, dan dengan demikian pemancar terdekat. Melakukan ini untuk semua penerima akan menjadi $\mathcal{O}(\log n)$ $\mathcal{O}(n\log n)$ , kasus terburuk. $\mathcal{O}(n\log n)$

Setiap sel dalam diagram Voronoi adalah poligon cembung, mungkin tidak terikat.

...

Jumlah simpul [dari diagram Voronoi dari n situs] V ≤ 2n-5

- www.cs.arizona.edu

Setiap poligon dalam diagram Voronoi adalah poligon cembung. Oleh karena itu, karena triangulasi poligon cembung membutuhkan waktu , sebagai jumlah sisi, kita dapat melakukan triangulasi setiap sel secara efisien. Jika Anda takut bahwa triangulasi dapat menjadi patologis (bahwa kita mungkin memiliki sel, masing-masing dengan sisi), maka pertimbangkan ini. Diagram Voronoi memiliki simpul (lihat kutipan di atas). Triangulasi diagram Voronoi adalah planar, dan begitu juga grafik yang jarang, dan dengan demikian memiliki tepi dan wajah. Jadi triangulasi sel tertentu mungkin diperlukan $\Theta(v)$ $v$ $n$ $n$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$

Realz Slaw
sumber