在集合A中找到所有点在集合B中的最近邻算法

Question

假设我们有两组点A、B，我们想要为集合A中的每个点找到其在集合B中最近的邻居。

有许多好的算法可以找到一个点的最近邻。是否有一些方法可以利用我们得到的a_1的信息，更有效地搜索a_2或集合中的其他点的最近邻？

我认为可以这样做：使用三角不等式获取每个B中的点与新点a_2之间可能距离的区间，并对区间的最大值和最小值进行排序，然后只搜索落在第一个区间内的B中的点。

- gstar2002

---

在您的上下文中，“effort”是什么意思？ - EvilTeach

计算距离d(x,y)。 - gstar2002

你可以对点设置任何限制吗？ - Cam

我不知道这是否是最优解的一部分，只是它与问题相关。http://en.wikipedia.org/wiki/K-d_tree - goat

Answer 1

1. 找到点集B的Voronoi图。
2. 在点集A和点集B的Voronoi图上应用扫描线算法。每当扫描线覆盖点集A中的某个点时，在Voronoi图的哪些边之间查看该点的位置。这将确定该点属于Voronoi图的哪个面，从而给出点集B中最近的点。

步骤2的细节：将所有被扫描线当前交叉的Voronoi图的边保留在某个有序容器中。当扫描线覆盖Voronoi图的某个顶点时，从/向容器中删除/添加与该顶点相连的边。要查看某个点位于哪些边之间，请获取该点在容器中的前/后继边。

时间复杂度为O((M+N) log M)，其中N = |A|，M = |B|。

- Evgeny Kluev

Answer 2

您可以从本特利的《编写高效程序》中受益，他在其中处理了旅行推销员问题的案例研究。他认识到的其中一个节省是两点之间的距离涉及到开方运算，这是昂贵的。进行开方运算可以得到实际距离，不进行开方运算可以得到可用于与其他相对值进行比较的数字。

我强烈推荐阅读这本书。它将使您的大脑处于正确的状态。

- EvilTeach

Answer 3

一个暴力的解决方案是使用集合B中最接近点的树状图。然后将集合A的每个点与树状图进行比较。您还可以使用Delaunay三角剖分创建树状图。

- Micromega