在一组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/
最佳答案
对于smallk来说，一个可行的选择是在原始点集的子集上重复使用O(nlogn)算法，在移动时删除点。更具体地说，保持形成最小对的一组点每次您查询下一个最近的对时，我们都将查询这些点内以及每个点与其他原始点之间的下一个最近的对，并从这两个对中选取较近的一个。
首先，从原始集合中除去除其中一个点以外的所有点，然后计算最近的一对对“最小集”中的每个点重复此操作，并保持整体最接近的对。当“最小集”的大小为O(j*nlogn)时，这将需要j时间来计算。
然后，通过find min（O(1)time）在大小为k的min max堆上查询“min set”中下一个最近的对，我们将在向“min set”添加点时构建该堆每次我们向“最小集合”添加点时，我们将计算“最小集合”（大小j）中的每个点与这些（最多）2个新点之间的距离，将它们插入到最小-最大堆中，然后根据需要删除尽可能多的元素，以便在k时间内再次使堆大小2j（最多O(jlogk)个元素）。
现在，我们取这两个值中较近的一对（如果相关的话从堆中删除-O(logk)时间），将这些点添加到“min set”中，并更新所述的min max堆，然后对其余的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/