algorithm - 连接二维空间中的任意两点

Question

有没有比 O(n^2) 更好的算法来用直线连接任意两点，只要它们的距离小于常数 t？

我正在考虑根据 x 坐标对点进行排序，然后在 [x-t, x+t] 内寻找另一个点。但最坏的情况仍然是 O(n^2)。任何想法？我们有什么特殊的数据结构可以加速吗？

Answer 1

一种可能有用的方法是为每个点计算一个桶:

int(x/t),int(y/t)

即点 (0.1,0.9)、(0.5,0.5)、(0.8,0.2) 都会进入同一个桶。

将所有点放入这些桶中，然后再次迭代点。

这种组织的原因是你只需要检查一个点与同一个桶中的点，或者 8 个相邻桶中的点。

在糟糕的情况下，这仍然可能是 O(n^2)(例如，如果所有点都在彼此的 t 范围内)，但在某些情况下它可能会有所帮助。