Biaya melakukan sekitar. pencarian tetangga terdekat di quadtree lewati

CATATAN : Pertanyaan telah dinyatakan kembali dalam jawaban saya: Dengan asumsi sekarang kita dapat menemukan leluhur saudara kandung terendah dalam waktu $O(1)$ , dapatkah JST benar-benar dilakukan dalam $O(\log n)$ ?

Quadtrees adalah indeks spasial yang efisien. Saya punya teka-teki dengan implementasi pencarian tetangga terdekat dalam struktur quadtree terkompresi seperti yang dijelaskan dalam [2]. (Tanpa masuk ke dalam perincian, pencarian dilakukan secara top-down di sepanjang apa yang disebut kuadrat sama-sama, berakhir pada simpul ekor dari jalur yang sama. Pada gambar terlampir ini mungkin salah satu dari simpul di tenggara diisi dengan titik-titik.)

Agar algoritme mereka berfungsi, kita harus memelihara untuk setiap simpul - bujur sangkar dengan setidaknya dua kuadran tidak kosong - pointer untuk setiap simpul leluhur terendah (terdekat dalam hierarki) di masing-masing dari empat arah (utara, barat, selatan). , timur). Ini ditunjukkan oleh panah hijau untuk leluhur node 'barat (panah menunjuk pada pusat alun-alun leluhur).

Makalah mengklaim pointer ini dapat diperbarui dalam O (1) selama penyisipan dan penghapusan titik. Namun ketika melihat penyisipan titik hijau, sepertinya saya perlu memperbarui sembarang jumlah pointer, dalam hal ini enam dari mereka.

Saya berharap ada trik untuk melakukan pembaruan pointer ini dalam waktu yang konstan. Mungkin ada bentuk tipuan yang bisa dieksploitasi?

EDIT:

Bagian yang relevan dari makalah ini adalah 6.3, di mana tertulis: "jika jalan memiliki tikungan, maka selain leluhur terendah , kita juga harus mempertimbangkan untuk masing-masing dari arah yang terendah leluhur yang mengarah ke arah itu [...] Menemukan kuadrat ini dari dapat dilakukan dalam waktu per kotak jika kita mengaitkan pointer tambahan ke setiap kotak di menunjuk ke leluhur terdekatnya untuk setiap arah Pointer ini juga dapat diperbarui dalam waktu selama penyisipan atau penghapusan suatu titik. "q 2 d q q O ( 1 ) 2 d Q 0 O ( 1 $log(c/ε)$$q$$2^d$$q$$q$$O(1)$$2^d$$Q_0$$O(1)$

[2]: Eppstein, D. dan Goodrich, MT dan Sun, JZ, “The Skip Quadtree: Struktur Data Dinamis Sederhana untuk Data Multidimensi,” dalam Prosiding simposium tahunan ke dua puluh satu tentang geometri komputasi, hal. 296—305 2005

Seperti David, saya tidak tahu mengapa Jonathan berkomentar tentang petunjuk kedua. Mereka tidak dibutuhkan. Seperti yang disebutkan David di atas, properti penting adalah bahwa ketika kita melakukan lokasi titik ke daun v di Q_0, cukup untuk mengingat simpul saudara (dan kotak mereka) di lompatan quadtree. Saat kami memproses kotak dari P, kami melakukan lokasi titik untuk kotak daun terdekat dengan titik kueri kami, memasukkan kotak saudara saat kami turun. Kedengarannya seperti ini akan kurang lebih sama dengan jawaban Anda. Selain itu, prosedur ini sangat mirip, misalnya, dengan bagaimana perkiraan titik lokasi dilakukan dalam makalah berikut: Arya, Sunil dan Mount, David M. dan Netanyahu, Nathan S. dan Silverman, Ruth dan Wu, Angela Y., "Algoritma optimal untuk perkiraan dimensi tetangga terdekat yang mencari", JACM, 1998. Memang,

Orang dapat berpikir tentang melewatkan quadtree sebagai implementasi daftar-lewati dari struktur data yang menyimpan poin sesuai dengan z-order mereka. Ini (bisa dibilang) setidaknya secara konsepsi lebih sederhana ...

Lihat bab 2 di sini: http://goo.gl/pLiEO .

Dan ya, dengan asumsi Anda dapat melakukan beberapa operasi z-order dasar dalam waktu konstan, Anda pasti dapat melakukan JST dalam waktu logaritmik. Bab yang disebutkan di atas juga menunjukkan bahwa tidak ada cara untuk menghindari operasi yang aneh jika seseorang ingin quadtrees terkompresi. Perhatikan, bahwa operasi LCA tidak diperlukan ...

Saya juga secara intuitif merasa bahwa seseorang dapat hidup tanpa pointer itu, dan karena saya harus bertahan semua node ke harddisk di beberapa titik, setiap pengurangan pointer itu bagus.

Ide saya kira-kira sebagai berikut: Terlepas dari titik kandidat terbaik (daun) , kami juga melacak jarak terburuk di setiap putaran, . Jarak terburuk adalah maksimum jarak semua sudut dari simpul ke titik kueri , tidak peduli apakah berada di dalam kuadrat atau di luar. r m a x d i s t ' ( v , q ) q v $l_{best}$$r_{max}$${dist}'(v,q)$$q$$v$$v$

Putaran seperti ini: Jika kosong, kembalikan , jika ada. Jika tidak delete-min memberikan saat ini di . Inisialisasi ke (atau atur ke jika belum ada kandidat terbaik yang diamati). Pertama, uji setiap anak non-kosong di . Jika anak ini adalah , perbarui dan jika perlu. Jika adalah simpul, hitung dan , yang terakhir adalah jarak terbaik: Entah nol, jikal b e s t p 0 Q 0 r m a x l b e s t ∞ p 0 Q 0 q $P$$l_{best}$$p_0$$Q_0$$r_{max}$$l_{best}$$\infty$$p_0$$Q_0$$q$$l_{best}$$r_{max}$$q$${dist}'(q,v)$${dist}(q,v)$$v$ terletak di dalam , atau jarak terpendek dari semua sudut ke .$q$$q$$v$

Jika , lupakan , jika tidak simpanlah. Jika jumlah node terus adalah , mendorong orang-node ke . Akhir babak. q ≥ 2 ${dist}(q,v) > r_{max}$$q$$\geq 2$$P$

Jika tidak, lanjutkan mirip dengan pencarian asli: Cari , node yang sesuai dengan di tertinggi , dan mulai dari sana: Sekali lagi, bukannya meminta anak berjarak sama untuk turun ke, uji semua anak sesuai dengan prosedur sebelumnya , yaitu, lewati mereka yang jarak terbaiknya melebihi . Jika setelah tes ini seorang anak tetap, turun ke sana dan ulangi. Jika tidak ada anak yang tersisa, buka dan ulangi. Jika tes dilakukan di , putaran selesai.p 0 Q j r m a x Q j - 1 Q $q$$p_0$$Q_j$$r_{max}$$Q_{j-1}$$Q_0$

Pada saat ini, saya tidak tahu apakah ini menjamin untuk menemukan tetangga terdekat dalam setiap kasus yang mungkin, atau bahwa itu berkinerja sebaik algoritma asli. Juga jika inisialisasi cukup atau tidak. Dan apa yang harus menjadi prioritas dalam - masih jarak terbaik?$r_{max}$$P$

EDIT (April 2013)

Saya sekarang telah melakukan lebih banyak eksperimen dengan klarifikasi algoritma di atas yang menggunakan definisi node 'ekuipoten' alih-alih simpul equistabbing, berdasarkan properti yang turun ke simpul seperti itu tidak mengubah area yang dicakup oleh bentuk kueri sejauh ini. .$r_{max}$

Sayangnya, kita dapat membuat kasus patologis (lihat gambar di bawah; titik kueri adalah bagian bawah tengah) di mana kinerja menurun ke putaran .$O(\sqrt n)$

$O(\epsilon^{1−d}(\log n+\log \epsilon^{−1}))$

$\epsilon = 1$$v$

$Q_0$

$O(\sqrt n)$$d = 2$$\epsilon = 1$$O(\log n)$

Jadi, kecuali saya kehilangan sesuatu yang penting, algoritma tidak dapat mencapai kecepatan yang dinyatakan. Ada komentar atau ide?