给定两个（大）点集，如何有效地找到彼此最接近的对？ [英] Given two (large) sets of points, how can I efficiently find pairs that are nearest to each other?

问题描述

我需要解决一个计算问题，归结为寻找两组之间最接近的点对。问题是这样的：

I need to solve a computational problem that boils down to searching for reciprocally-nearest pairs of points between two sets. The problem goes something like this:

给定欧氏空间中的一组点A和一组点B，找到所有对（a，b）使得b为

Given a set of points A and a set of points B in euclidean space, find all pairs (a,b) such that b is the closest point in B to a and a is the closest point in A to b.

集合A和B的大小大致相等，我们称此大小为B。 N。对于我的特定问题，N大约为250,000。

The sets A and B are of approximately equal size, and we will call this size N. For my particular problem N is approximately 250,000.

蛮力解决方案是将每个点与每个其他点进行比较，这具有二次时间复杂度。

The brute force solution is to compare every point against every other point, which has quadratic time complexity. Is there any more efficient algorithm for doing this?

推荐答案

一种数据结构，当我不得不进行最近邻居搜索时，它非常有用。是一棵 k d树。 Wikipedia 有一个很好的概述，并且这是对如果您正在实现自己的算法（尽管一个库可能已经存在-您不会提及正在使用的语言）。关于 k d树的最重要的事情是它允许在O（log N）时间内执行最近邻搜索。

A data structure I found very useful when I had to do nearest neighbour searches was a kd-tree. Wikipedia has a nice overview and this is an excellent in-depth discussion of the algorithm if you're implementing your own (although a library may well exist already - you don't mention which language you're using). The most important thing about a kd-tree is that it allows nearest-neghbour searches to be performed in O(log N) time.

这样，您可以在O（N log N）时间中生成两个列表-A的成员及其在B中的最近邻居以及B的成员及其在A中的最近邻居-。然后，您可以比较列表以查看匹配的对。天真地做，那是O（N ^ 2），尽管您也许可以想到一种更快地完成它的方法。

In that way, you could produce two lists of - the members of A and their nearest neighbour in B and the members of B and their nearest neighbour in A - in O(N log N) time. Then, you could compare the lists to see which pairs match. Done naively, that's O(N^2), though you might be able to think of a way to do it faster.

[edit] ;这是我的第二个想法：

[edit] You've got me thinking; here's my second thought:

for(a in A)
    b := nearest(B, a)
    if a = nearest(A, b)
        add (a, b) to results
    end if
end for

function nearest(X, y)
    return nearest member of set X to point y
end function

根据我的估算，即为O（N log N）。

By my reckoning, that's O(N log N).

这篇关于给定两个（大）点集，如何有效地找到彼此最接近的对？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！