Estrutura de dados do vizinho mais próximo para espaço de configuração não euclidiano

Estou tentando implementar uma estrutura de vizinho mais próximo para uso em um planejador de movimento RRT. Para fazer melhor do que uma pesquisa linear por força bruta do vizinho mais próximo, gostaria de implementar algo como uma árvore kd. No entanto, parece que a implementação clássica da árvore kd pressupõe que cada dimensão do espaço possa ser dividida em "esquerda" e "direita". Essa noção não parece se aplicar a espaços não euclidianos como SO (2), por exemplo.

Estou trabalhando com um braço manipulador serial com links totalmente rotacionais, o que significa que cada dimensão do espaço de configuração do robô é SO (2) e, portanto, não euclidiana. O algoritmo kd-tree pode ser modificado para lidar com esses tipos de subespaços? Caso contrário, existe outra estrutura de vizinho mais próximo que possa lidar com esses subespaços não euclidianos e ainda assim fácil de atualizar e consultar? Também dei uma olhada na FLANN , mas na documentação deles não estava claro se eles podem lidar com subespaços não euclidianos.

Você está certo de que os kd-trees geralmente funcionam apenas em pequenos espaços métricos euclidianos. Porém, há muito trabalho para aplicações vizinhas gerais mais próximas em espaços métricos (em qualquer lugar em que você possa definir essencialmente uma função de distância).

O trabalho clássico é sobre árvores de bola , que foram generalizadas em árvores métricas .

Há algum trabalho mais novo chamado árvores de cobertura que ainda possui código GPL. Eu queria analisar as características de desempenho entre essas árvores e kd-trees há mais de dois anos.

Felizmente, isso se adapta à sua aplicação.

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

$O(sqrt(N))$