Структура данных ближайшего соседа для неевклидового пространства конфигурации

Я пытаюсь реализовать структуру ближайшего соседа для использования в планировщике движения RRT. Чтобы сделать лучше, чем линейный поиск ближайших соседей, я хотел бы реализовать что-то вроде kd-дерева. Тем не менее, кажется, что классическая реализация дерева kd предполагает, что каждое измерение пространства может быть разделено на «левое» и «правое». Это понятие, кажется, не относится к неевклидовым пространствам, таким как, например, SO (2).

Я работаю с рычагом последовательного манипулятора с полностью вращающимися звеньями, что означает, что каждое измерение пространства конфигурации робота является SO (2) и, следовательно, неевклидовым. Можно ли изменить алгоритм дерева kd для обработки таких подпространств? Если нет, есть ли другая структура ближайшего соседа, которая может обрабатывать эти неевклидовы подпространства, в то же время проста для обновления и запроса? Я также взглянул на FLANN , но из их документации мне не было ясно, могут ли они обрабатывать неевклидовы подпространства.

Вы правы, что kd-деревья обычно работают только в небольших евклидовых метрических пространствах. Но есть много работы для общих приложений ближайших соседей в метрических пространствах (где угодно вы можете определить функцию расстояния по существу).

Классическая работа посвящена деревьям шаров , которые затем были обобщены до метрических деревьев .

Существует более новая работа, называемая деревьями покрытия, в которой даже есть код под GPL. Я хотел изучить характеристики производительности между этими деревьями и деревьями kd уже более двух лет.

Надеюсь, это подходит для вашего приложения.

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

$O(sqrt(N))$