1

我在多维空间中有大量点。而且我想为任何给定点找到几个邻居（在附近）（要求是避免扫描所有点）。

我想知道我的解决方案是否合适：

预处理：

  1. 定义一组正交轴
  2. 对每个轴上的每个点进行投影
  3. 每个投影都与其到轴起点的距离（键）和点的标识符（值）相关联。索引投影- 将它们全部放入排序集（例如树集）
dist = distance of projection to the start point of axis
point_num = number of point 
sorted_set.put( dist, point_num )

要查找任何给定点的邻居：

  1. 找到它在每个轴上的投影
  2. 使用 idex - 在每个 exis 上找到最近的投影
  3. 寻找实际的邻居——所有结果的交集
dx = radius of neighborhood (some constant) 

dist_1 = distance of projection of given point to start point of axis_1 
list_1 = sorted_set_1.get_sub_set( dist_1 - dx, dist_1 + dx )

dist_2 = distance of projection of given point to start point of axis_2
list_2 = sorted_set_2.get_sub_set( dist_2 - dx, dist_2 + dx ) 

return intersection_of( list_1, list_2 )

这是一个简单的例子：

在此处输入图像描述

相交[2, 4, 1]并[4, 5]产生答案[4]

请指出我，如果我在算法中犯了任何错误

谢谢

4

1 回答 1

1

您尚未向我们提供有关如何构建实际邻居集的说明，在这种情况下[2, 4, 1]和[4, 5]. 为什么你从一个索引中选择 3 个元素而从另一个索引中选择 2 个？

你还说你想找几个邻居。几个是多少，或者它应该是你的功能的输入？在示例中您只找到一个，算法是否应该决定您想要多少？

如果所有点都在您的一个轴上的一条线上，会发生什么情况？那么一组肯定包含所有元素。

于 2013-02-15T14:50:53.530 回答