是否有可能比 O(n^2) 更快地找到一组 n 个点中的 k 对 最近点？
我知道我可以在 O(nlogn) 中计算最近的一对点，但是使用该算法，并不是所有的距离都被计算出来，所以我不能返回顶部的 k最近的点对。
如果使用“蛮力”方法计算点的所有边的距离，这个问题是微不足道的，但这有 [n * (n-1) ]/2 我想找到更高效的方法。
编辑: 在此处查看最接近的对算法: https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
最佳答案
小型 k 的一个可行选择将使用您的 O(nlogn)算法在原始点集的子集上重复，边走边删除点。更具体地说，保留一组构成最小对的点。每次您查询下一个最近对时，我们将在这些点内以及每个点与其余原始点之间查询下一个最近对，并取两对中较近的一个。
首先，从原始集中删除这些点中的一个，然后计算最接近的一对。对这个“最小集合”中的每个点重复此操作，并保留总体上最接近的对。这需要 O(j*nlogn)计算时间，当“最小集”的大小为 j 时.
然后，通过查找最小值(O(1) 时间)在大小为 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)时间。
关于algorithm - 在 O(nlogn) 时间内从一组 n 个点中获取前 k 个最接近的点对？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54990512/