算法找到所有点集合A中的最近邻居集合B [英] Algorithm to find for all points in set A the nearest neighbor in set B

问题描述

假设我们有两套分A，B的，我们希望找到集合A中的其最近的邻居集合B

每一个点

有很多很好的算法来找到最邻近的一个点。是否有某种方式来使用我们得到的A_1的信息，更有效地搜索该组中的近邻A_2或其他点？

我想是这样的：用三角inequlity以获取在B和新点A_2每个点之间可能存在距离的间隔和排序区间的最大值和最小值，然后我可以在2搜索只点这落在第一间隔

解决方案

1. 找到 Voronoi图以集合B点。
2. 套用扫描线算法在集合A与B的Voronoi图的点只要扫线覆盖了某个点从集合A，看的Voronoi边缘关系图的该点所在。这允许以确定这点所属Voronoi图的哪个面。这给从集合B的最近点。

第2步详细信息：保持Voronoi图，目前由扫描线相交的所有边缘，在一些有序的容器。当扫描线涵盖Voronoi图的一些顶点，删除/添加的边缘，入射到这个顶点，自/至容器。一看，边缘之间的一些点所在，让继任者/ predecessor边缘，这点在容器中。

时间复杂度为O（（M + N）登录M）。 N = | A |，M = | B |。

Suppose we have two sets of points A, B, and we want to find for every point in set A its nearest neighbor in set B.

There are many good algorithms to find the nearest neighbor for one point. Is there some way to use the information we got for a_1, to more efficiently search for the nearest neighbor for a_2 or other points in the set?

I am thinking something like: use triangular inequlity to get a interval for possible distance between every point in B and new point a_2, and sort the max and min of the intervals, and then I can search only the points in B which falls in the first interval.

解决方案

1. Find Voronoi diagram for points of set B.
2. Apply a Sweep line algorithm over points of set A and Voronoi diagram of set B. Wherever sweep line covers some point from set A, look between which edges of Voronoi diagram this point is located. This allows to determine to which face of Voronoi diagram this point belongs. Which gives the closest point from set B.

Details for step 2: Keep all edges of Voronoi diagram, currently intersected by sweep line, in some ordered container. When sweep line covers some vertex of Voronoi diagram, remove/add edges, incident to this vertex, from/to container. To look, between which edges some point is located, get successor/predecessor edges to this point in container.

Time complexity is O((M+N) log M). N = |A|, M = |B|.

这篇关于算法找到所有点集合A中的最近邻居集合B的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！