分而治之:查找距离小于D的所有点对

Question

给定n个点(x，y坐标)，我需要使用分而治之算法找到距离小于D的所有点对。

最初，我考虑使用类似的方法作为最近点问题，但因为现在距离D是一个常数，所以我们可以有无限多的点位于分割区域，而不是最近点问题中的常数8。因此运行时间将是O(n^2)，这并不比Brute-force更好。

任何想法或提示都将不胜感激。

Answer 1

在平均情况下提高效率的一种方式是首先使用典型的分治方法对点的坐标( x，y)进行排序，如果x相同，则将点的坐标(x，y)与x相关，并与y相关(非常类似于字符串的排序方式)。

然后从排序后的数组中的第一个点（我称之为枢轴点）开始检查，知道距离 D 和枢轴点的 x 和 y 值，我们可以计算 x 值的上限。同样对于范围内的每个 X，我们还可以计算其上下 y 范围，这将问题的其余部分转化为嵌套范围迭代问题，迭代直到超出范围（要找到 y 迭代的起始位置，您可以需要对具有相同 x 的数据集使用二分查找）。

例如，我们有一组点(1,0) (5,0) (3,1) (1,3) (3,4)，我们需要找到距离在2以内的点对。首先对这些点进行排序，我们得到(1,0) (1,3) (3,1) (3,4) (5,0)。将(1,0)设为轴心点，我们可以计算x的上限为3，因此我们不必关心(5,0)。然后，我们可以检查x= 1的点集，并计算y的下限/上限-2和2，以再次在x=1的点集中查找下y。y在-2和2之间的点是有效的点。重复上述步骤，我们最终可以找到所有有效的点对。