algorithm - 在 O(nlogn) 时间内从一组 n 个点中获取前 k 个最接近的点对？

Question

是否有可能在一组 n 点中找到k 对最近点比 快O(n^2)？

我知道我可以计算 中最近的点对O(nlogn)，但是使用该算法，并非所有距离都被计算，因此我无法返回前k 个最近的点对。

如果使用“蛮力”方法计算点的所有边缘的距离，这个问题是微不足道的，但这具有复杂性[n * (n-1)]/2，我想找到更有效的方法。

编辑：在此处查看最接近的配对算法： https ://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/

标签： algorithmrecursiondata-structuresclosest-points

Answer 1

一个可行的小选项是在原始点集的子集上重复k使用您的O(nlogn)算法，并在进行时删除点。更具体地说，保留一组形成最小对的点。每次您查询下一个最接近的对时，我们都会在这些点内以及每个点与其余原始点之间查询下一个最接近的对，并取两对中较近的一对。

首先，从原始集合中删除除一个之外的所有点，并计算最接近的对。对这个“最小集合”中的每个点重复此操作，并保持整体最接近的对。O(j*nlogn)当“最小集”为 size 时，这将需要时间来计算j。

然后，通过在我们将点添加到“最小集”时构建O(1)的最小-最大堆上的find-min (time) 查询此“最小集”中的下一个最接近的对。k每次我们将点添加到“最小集”时，我们都会计算“最小集”中的每个点（大小j）与这些（最多）2 个新点之间的距离，将它们插入到我们的最小-最大堆中，然后删除尽可能多的元素，以便及时k重新调整堆大小（最多2j元素）O(jlogk)。

现在，我们取这两个中最接近的对（如果相关O(logk)时间从堆中删除），将这些点添加到我们的“最小集”并按照描述更新最小-最大堆，然后对剩余的k-j最接近的对重复。总的来说，这需要O((k^2)nlogn + (k^2)logk + klogk) = O((k^2)(nlogn + logk)) = O((k^2)nlogn)时间。