Struktur data tetangga terdekat untuk ruang konfigurasi non-Euclidean

Saya mencoba menerapkan struktur tetangga terdekat untuk digunakan dalam perencana gerak RRT. Untuk melakukan yang lebih baik daripada pencarian tetangga terdekat terdekat, saya ingin mengimplementasikan sesuatu seperti kd-tree. Namun, sepertinya implementasi klasik dari kd-tree mengasumsikan bahwa setiap dimensi ruang dapat dibagi menjadi "kiri" dan "kanan". Gagasan ini tampaknya tidak berlaku untuk ruang non-Euclidean seperti SO (2), misalnya.

Saya bekerja dengan lengan manipulator serial dengan tautan rotasi penuh, artinya setiap dimensi ruang konfigurasi robot adalah SO (2), dan karenanya non-Euclidean. Dapatkah algoritma kd-tree dimodifikasi untuk menangani subruang semacam ini? Jika tidak, apakah ada struktur tetangga terdekat yang dapat menangani subruang non-Euclidean ini sementara masih mudah diperbarui dan di-query? Saya juga melihat FLANN , tetapi tidak jelas bagi saya dari dokumentasi mereka apakah mereka dapat menangani subruang non-Euclidean.

Anda benar bahwa pohon kd biasanya hanya bekerja di ruang metrik Euclidean kecil. Tapi, ada banyak pekerjaan untuk aplikasi tetangga terdekat umum di ruang metrik (di mana saja Anda dapat mendefinisikan fungsi jarak pada dasarnya).

Karya klasiknya adalah pada pohon bola , yang kemudian digeneralisasikan menjadi pohon metrik .

Ada beberapa pekerjaan baru yang disebut pohon penutup yang bahkan memiliki kode GPL. Saya ingin melihat karakteristik kinerja antara pohon-pohon ini dan pohon kd selama lebih dari dua tahun sekarang.

Semoga sesuai dengan aplikasi Anda.

$sqrt(N)$ompl::NearestNeighborsSqrtApprox< _T >

$O(sqrt(N))$