15
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ By the way, approximate nearest-neighbors is fine too (even preferred, if the speedup is considerable) $\endgroup$
    – giogadi
    Oct 23 '12 at 20:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark Booth ♦
    Oct 23 '12 at 21:18
  • $\begingroup$ Thanks Mark, I was actually uncertain about how long to wait before accepting the answer. $\endgroup$
    – giogadi
    Oct 23 '12 at 21:21
6
$\begingroup$

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.

Hopefully, that fits your application.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry to unaccept; just following another commenter's advice to give this question a few more days to "stew". I really found your answer helpful, though! $\endgroup$
    – giogadi
    Oct 23 '12 at 21:22
  • $\begingroup$ Booo. Just kidding. I am just happy that you found this helpful. $\endgroup$
    – Chris Mansley
    Oct 23 '12 at 22:26
0
$\begingroup$

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))$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.