algorithm - 将一组点分组到最近的对

Question

我需要一个解决以下问题的算法:

我在平面上得到了一组二维点 P = { (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) }。我需要按以下方式将它们成对分组:

1. 找到 P 中最近的两个点 (x_a, y_a) 和 (x_b, y_b)。
2. 将 <(x_a, y_a), (x_b, y_b)> 对添加到结果集 R。
3. 从 P 中删除 <(x_a, y_a), (x_b, y_b)>。
4. 如果初始集合P不为空，转第一步。
5. 返回对 R 的集合。

那个朴素的算法是 O(n^3)，使用更快的算法搜索最近的邻居可以改进到 O(n^2 logn)。可以做得更好吗？

如果这些点不在欧几里德空间中怎么办？

一个例子(结果组用红色圈圈起来):

Answer 1

将所有点放入 http://en.wikipedia.org/wiki/R-tree 中(time O(n log(n))) 然后为每个点计算到其最近邻居的距离。将点和初始距离放入优先队列。初始化一组空的删除点和一组空的对。然后执行以下伪代码:

while priority_queue is not empty:
    (distance, point) = priority_queue.get();
    if point in removed_set:
        continue
    neighbor = rtree.find_nearest_neighbor(point)
    if distance < distance_between(point, neighbor):
        # The previous neighbor was removed, find the next.
        priority_queue.add((distance_between(point, neighbor), point)
    else:
        # This is the closest pair.
        found_pairs.add(point, neighbor)
        removed_set.add(point)
        removed_set.add(neighbor)
        rtree.remove(point)
        rtree.remove(neighbor)

其中最慢的部分是最近邻搜索。 R 树不保证那些最近邻搜索将O(log(n))。但他们往往是。此外，您不能保证每个点都会进行 O(1) 邻居搜索。但通常你会。所以平均性能应该是 O(n log(n))。 (我可能缺少对数因子。)