我知道这可能是重复的，但它似乎是“最近点对”算法的一种变体。
给定单位正方形中的一组N个点 (x, y) 和距离d，找到所有点对，使得它们之间的距离最多为d。
对于大N，蛮力方法不是一种选择。除了“扫线”和“分而治之”的方法，还有更简单的解决方案吗？这对点是无向图的边缘，我需要遍历它并说出它是否连接（我已经使用 DFS 做过，但是当 N = 100 万时它永远不会完成！）。
欢迎任何伪代码、评论或想法，谢谢！
编辑：我在 Sedgewick 的书上找到了这个（我现在正在查看代码）：
当 N 足够大时，程序 3.18 使用一个二维的链表数组将程序 3.7 的运行时间提高了大约 1/d2。它将单位正方形分成大小相等的较小正方形的网格。然后，对于每个正方形，它建立一个包含所有落入该正方形的点的链表。二维数组提供了立即访问靠近给定点的点集的能力；链表提供了存储它们可能落入的点的灵活性，而我们不必提前知道有多少点落入每个方格中。
我们实际上是在寻找以 (x,y) 为中心、半径为 d 的圆内的点。
包围圆的正方形是中心 (x,y) 和边 2d 的正方形。这个正方形之外的任何点都不需要检查，它已经出来了。因此，如果 abs(xa - x) > d 或 abs(ya -yb) > d，则点 a (xa, ya) 出局。
由该圆包围的正方形也是中心 (x,y) 和对角线 2d 的正方形。这个正方形之外的任何点都不需要检查，它在里面。所以，如果 abs(xa - x) < (d * 1.412) 或 abs(ya -yb) < ( d * 1.412）。
这两个简单的规则相结合，大大减少了要检查的点数。如果我们按它们的 x 对点进行排序，过滤可能的点，按它们的 y 排序，我们就会得到我们真正需要计算完整距离的点。
对于任何给定点，您可以使用曼哈顿距离（x-delta 加 y-delta）启发式过滤掉大部分不在距离“d”内的点 - 过滤掉曼哈顿距离大于 (sqrt (2) * d)，然后对剩余的点进行昂贵且精确的距离测试。