# Nearest-neighbor data structure for non-Euclidean configuration space

I'm trying to implement a nearest-neighbor structure for use in an RRT motion planner. In order to do better than a linear brute-force nearest-neighbor search, I'd like to implement something like a kd-tree. However, it seems like the classical implementation of the kd-tree assumes that each dimension of the space can be split into "left" and "right". This notion doesn't seem to apply to non-Euclidean spaces like SO(2), for instance.

I'm working with a serial manipulator arm with fully rotational links, meaning that each dimension of the robot's configuration space is SO(2), and therefore non-Euclidean. Can the kd-tree algorithm be modified to handle these kinds of subspaces? If not, is there another nearest-neighbor structure that can handle these non-Euclidean subspaces while still being easy to update and query? I also took a look at FLANN, but it wasn't clear to me from their documentation whether they can handle non-Euclidean subspaces.

• By the way, approximate nearest-neighbors is fine too (even preferred, if the speedup is considerable) – giogadi Oct 23 '12 at 20:10
• While you have accepted an excellent answer, it is usually a good idea to wait a few days before accepting an answer so that you don't discourage further answers which might provide other options. – Mark Booth Oct 23 '12 at 21:18
• Thanks Mark, I was actually uncertain about how long to wait before accepting the answer. – giogadi Oct 23 '12 at 21:21

You are correct that kd-trees typically only work in small, Euclidean metric spaces. But, there is lots of work for general nearest neighbor applications in metric spaces (anywhere you can define a distance function essentially).

The classic work is on ball trees, which then were generalized to metric trees.

There is some newer work called cover trees which even has GPL'ed code. I have wanted to look into the performance characteristics between these trees and kd-trees for more than two years now.

A simple option for approximate neighbor search in non-euclidean spaces is using $sqrt(N)$ samples in the search. This has been implemented in OMPL, see ompl::NearestNeighborsSqrtApprox< _T > Class Template Reference.
This reduces complexity to $O(sqrt(N))$.