我正在使用具有完全旋转连接的串行机械臂，这意味着机器人的配置空间为SO（2），因此为非欧几里得。可以修改kd-tree算法来处理这些子空间吗？如果不是，是否还有另一个最近邻居结构可以处理这些非欧几里得子空间，同时仍然易于更新和查询？我也看过FLANN，但是从他们的文档中我还不清楚他们是否可以处理非欧几里德子空间。
#1 楼
您是正确的，kd树通常仅在较小的欧几里德度量空间中工作。但是，对于度量空间中的一般最近邻应用程序有很多工作（可以在任何地方定义距离函数）。经典的工作是在球树上，然后将其推广到度量树。
有一些新的工作，称为覆盖树，甚至具有GPL编码。我想研究这些树和kd树之间的性能特征已经有两年多了。
希望它适合您的应用程序。
评论
$ \ begingroup $
对不起，我们无法接受；只是跟随另一个评论者的建议，给这个问题多几天的时间“炖”。不过，我确实发现您的答案很有帮助！
$ \ endgroup $
– giogadi
2012年10月23日在21:22
$ \ begingroup $
嘘。开玩笑。我很高兴您发现这很有帮助。
$ \ endgroup $
–克里斯·曼斯利（Chris Mansley）
2012年10月23日在22:26
#2 楼
在非欧几里得空间中进行近似邻居搜索的一个简单选项是在搜索中使用$ sqrt（N）$个样本。这已在OMPL中实现，请参见ompl::NearestNeighborsSqrtApprox< _T >类模板参考。将复杂度降低到$ O（sqrt（N））$。
评论
顺便说一句，近似最近的邻居也很好（如果加速比很大，甚至可以选择）虽然您接受了一个很好的答案，但是通常最好等待几天再接受一个答案，这样您就不会再阻止可能提供其他选择的其他答案了。
谢谢马克，实际上我不确定接受答案之前要等待多长时间。