Pada sebagian besar (semua?) Implementasi Metode Multipole Cepat (FMM), oktri digunakan untuk menguraikan domain yang relevan. Secara teoritis, oktri memberikan ikatan volumetrik sederhana, yang berguna untuk membuktikan runtime O (n) FMM. Di luar dasar pemikiran teoretis ini, apakah ada manfaat menggunakan Octree di atas struktur data pohon atau trie lainnya?
Menentukan daftar interaksi mungkin lebih mudah dengan sebuah octree karena sebuah sel akan tahu tetangga terdekatnya. Namun, daftar interaksi tidak perlu menggunakan traversal pohon yang lebih dinamis seperti Dual Tree Traversal .
Alternatifnya adalah pohon kd. Satu kelemahan teoretis yang mungkin adalah bahwa konstruksi membutuhkan operasi pencarian median yang mahal. Namun, ada versi kd-tree yang tidak memerlukan median temuan selama konstruksi - walaupun dengan partisi ruang yang kurang efisien. Dari segi implementasi, pohon kd sangat sederhana.
Alternatif yang bahkan lebih radikal mungkin adalah R-tree .
Jadi, pertanyaan saya adalah: Bagaimana dengan Octrees yang menjadikannya pilihan terbaik untuk FMM?
sumber
Jawaban:
Komentar di atas memberikan beberapa alasan yang sangat baik untuk menggunakan octrees (yaitu, membagi dua secara rekursif dua kubus komputasi di setiap dimensi sebagai lawan dari pembelahan ortogonal yang lebih umum). Simetri dan kesederhanaan menghitung daftar interaksi adalah nilai tambah yang besar.
Saya berpendapat bahwa mungkin fitur yang paling penting yang dibawa oleh oktaf ke meja adalah bahwa teorema tambahan yang menjamin FMM secara sistematis puas untuk interaksi zona jauh yang tidak tergantung pada geometri dengan kriteria pemisahan yang sangat sederhana dari satu atau lebih "buffer". kotak. Dengan kata lain, representasi jumlah FMM dari bidang potensial dijamin akan menyatu dengan meningkatnya keteraturan dalam keadaan non-patologis.
sumber