将点集分组到最近的对

Question

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

我在平面上给出了一组2D点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-树(时间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)).(我可能会错过一个日志因子.)