假设我们有两组点 A、B，我们想为集合 A 中的每个点找到它在集合 B 中的最近邻居。
有很多很好的算法可以找到一个点的最近邻。有什么方法可以使用我们为 a_1 获得的信息，以更有效地搜索 a_2 或集合中其他点的最近邻居？
我在想这样的事情：使用三角不等式来获取B中每个点与新点a_2之间可能距离的间隔，并对间隔的最大值和最小值进行排序，然后我只能搜索B中落入的点第一个间隔。
问问题
2940 次
3 回答
11
- 求集合 B 的点的Voronoi 图。
- 在集合 A 的点和集合 B 的 Voronoi 图上应用扫描线算法。无论扫描线覆盖集合 A 中的某个点，查看该点位于 Voronoi 图的哪些边缘之间。这允许确定该点属于 Voronoi 图的哪个面。这给出了集合 B 的最近点。
第 2 步的详细信息：将当前与扫描线相交的 Voronoi 图的所有边保留在某个有序容器中。当扫描线覆盖 Voronoi 图的某个顶点时，从/到容器删除/添加与该顶点相关的边。要查看某个点位于哪些边缘之间，请在容器中获取该点的后继/前继边缘。
时间复杂度为 O((M+N) log M)。N = |A|，M = |B|。
于 2012-10-21T18:08:03.540 回答
1
您可能会受益于阅读本特利的“编写高效程序”，其中他处理了旅行推销员程序的案例研究。他认识到的一项节省是，两点之间的差异涉及取平方根，这很昂贵。取平方根给你实际距离，不取平方根给你一个数字，可以用来与其他相对值进行比较。
我强烈推荐阅读这本书。它会把你的大脑放在正确的位置。
于 2012-10-21T17:50:21.653 回答
0
蛮力解决方案可能是使用集合 B 的最近点的树状图。然后将集合 A 的每个点与树状图进行比较。您还可以使用 delaunay 三角剖分创建树状图。
于 2014-05-30T09:04:25.760 回答