Implementasi pohon partisi?

11

Apakah pohon partisi pernah diimplementasikan?

Di sini, saya berbicara tentang pohon partisi dari geometri komputasi. Versi paling awal (paling dekat) di antaranya adalah karena Matousek dan yang lainnya, dan yang terbaru Timothy Chan:

https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf

Kedengarannya gila bagi saya bahwa ini belum pernah diterapkan, tetapi googling muncul tidak ada implementasi yang pernah dilaporkan siapa pun.

ds.data-structures implementation computational-geometry Pat Morin
sumber
Dari mana kutipan itu? Pembaca PDF saya tidak menemukannya di kertas T. Chan yang ditautkan dengan Anda.
jbapple
Itu dari naskah, bukan kertas Chan. Saya hanya ingin memverifikasi ini selengkap mungkin sebelum dipublikasikan.
Pat Morin
6
Saya tidak tahu konteks pertanyaan ini, tetapi: (1) Jika Anda meninjau sebuah naskah, saya rasa tidak apa-apa untuk membagikan bagian dari naskah yang sedang ditinjau seperti ini. (2) Makalah tidak boleh membuat klaim seperti itu karena meskipun benar, itu tidak dapat diverifikasi. Misalnya, tidak ada yang bisa mengesampingkan kemungkinan seseorang telah mengimplementasikannya sebagai proyek pribadi dan tidak pernah repot untuk membaginya secara publik.
Tsuyoshi Ito
1
Terima kasih atas sarannya. Itu adalah naskah tesis yang ditulis oleh muridku. Saya mungkin akan menguraikan kembali sebagai: meskipun mencari dengan seksama, kami tidak mengetahui adanya implementasi pohon partisi. (Mencari dengan saksama adalah apa yang saya lakukan sekarang, sebagian dengan pertanyaan ini.)
Pat Morin
2
Bisakah Anda menyederhanakan pertanyaan dengan menghapus kutipan dari naskah? Saat ini posting Anda menyiratkan dua pertanyaan (tidak ada yang secara eksplisit dinyatakan): (1) Bagaimana saya harus memeriksa kebenaran klaim bahwa pohon partisi tidak pernah dilaksanakan? Jawab: Seharusnya tidak. (2) Apakah orang tahu implementasi pohon partisi? Saya tidak tahu jawaban untuk bagian ini, tetapi saya pikir itu baik-baik saja sebagai pertanyaan. Satu-satunya masalah dengan (2) adalah tidak ada yang bisa mengatakan "tidak" untuk pertanyaan itu, tetapi Anda dapat menyimpulkannya setelah beberapa waktu jika tidak ada yang membuat implementasi.
Tsuyoshi Ito

Jawaban:

3

Menurut definisi dalam makalah yang ditautkan pada halaman 5, pernyataan itu salah. Pohon partisi ruang biner (BSP) telah digunakan selama puluhan tahun pada grafik komputer untuk mempercepat permintaan spasial, seperti halnya quadtrees dan octrees . Pohon Kd digunakan secara luas dalam pembelajaran mesin untuk mempercepat pencarian tetangga terdekat. Jika Anda sedikit menyipit, pohon keputusan juga cocok dengan definisi umum.

Neil Toronto
sumber
2
Ya, saya tahu itu. Apa yang saya belum temukan, bagaimanapun, adalah implementasi dari pohon BSP untuk set poin yang melakukan hal-hal mewah yang diperlukan untuk juga menjaga angka penikamannya dekat dengan O (sqrt (n)).
Pat Morin
3
Ini bukan pohon partisi dalam arti pertanyaan yang diajukan. Saya pikir OP secara khusus mencari struktur data untuk pencarian rentang ruang setengah.
Mikola