6

我知道这可能是重复的,但它似乎是“最近点对”算法的一种变体。

给定单位正方形中的一组N个点 (x, y) 和距离d,找到所有点对,使得它们之间的距离最多为d

对于大N,蛮力方法不是一种选择。除了“扫线”和“分而治之”的方法,还有更简单的解决方案吗?这对点是无向图的边缘,我需要遍历它并说出它是否连接(我已经使用 DFS 做过,但是当 N = 100 万时它永远不会完成!)。

欢迎任何伪代码、评论或想法,谢谢!

编辑:我在 Sedgewick 的书上找到了这个(我现在正在查看代码):

当 N 足够大时,程序 3.18 使用一个二维的链表数组将程序 3.7 的运行时间提高了大约 1/d2。它将单位正方形分成大小相等的较小正方形的网格。然后,对于每个正方形,它建立一个包含所有落入该正方形的点的链表。二维数组提供了立即访问靠近给定点的点集的能力;链表提供了存储它们可能落入的点的灵活性,而我们不必提前知道有多少点落入每个方格中。

4

2 回答 2

2

我们实际上是在寻找以 (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 排序,我们就会得到我们真正需要计算完整距离的点。

于 2013-04-05T14:30:10.087 回答
0

对于任何给定点,您可以使用曼哈顿距离(x-delta 加 y-delta)启发式过滤掉大部分不在距离“d”内的点 - 过滤掉曼哈顿距离大于 (sqrt (2) * d),然后对剩余的点进行昂贵且精确的距离测试。

于 2013-04-05T17:04:33.777 回答