假设我们有两组点 A、B，我们想为集合 A 中的每个点找到它在集合 B 中的最近邻居。
有很多好的算法可以找到一个点的最近邻点。有没有什么方法可以使用我们为 a_1 获得的信息，更有效地为 a_2 或集合中的其他点搜索最近的邻居？
我在想这样的事情:使用三角不等式获得 B 中每个点与新点 a_2 之间可能距离的区间，并对区间的最大值和最小值进行排序，然后我只能搜索 B 中的点落在第一个区间。
最佳答案
- 查找Voronoi diagram对于集合 B 的点。
- 申请Sweep line algorithm在集合 A 的点和集合 B 的 Voronoi 图上。只要扫描线覆盖集合 A 中的某个点，请查看该点位于 Voronoi 图的哪些边之间。这允许确定该点属于 Voronoi 图的哪个面。它给出了集合 B 中最近的点。
步骤 2 的详细信息:将 Voronoi 图的所有边(当前与扫描线相交)保存在某个有序容器中。当扫描线覆盖 Voronoi 图的某个顶点时，从/到容器移除/添加边缘，与该顶点相关。要查看某个点位于哪些边之间，请在容器中获取到该点的后继/前导边。
时间复杂度为 O((M+N) log M)。 N = |A|，M = |B|。
关于为集合 A 中的所有点查找集合 B 中最近邻居的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13000349/