在二维空间中连接任意两点

只要距离小于常数t，是否有任何算法比O（n^2）更好地通过直线连接任意两点？在二维空间中连接任意两点

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

2016-10-22 vinh0105

搜索“最接近的对问题”。 –

对t有限制吗？否则，如果所有点都在彼此的t内，那么你必须将每个点与每个其他点连接起来，这个点总是O（n^2）。 – TilmannZ

此外，搜索“空间连接”，例如[TOUCH]（https://infoscience.epfl.ch/record/186338/files/sigfp132-nobari_1.pdf）算法会查找所有点连接点在最大距离内。但是，您可以通过良好的通用多维索引实现类似的性能（如果需要，我可以推荐一个）。 – TilmannZ

一种方法，可以帮助是计算每个点如斗：

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

即点（0.1,0.9），（0.5,0.5），（0.8,0.2）将全部进入同一个桶。

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

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

在坏的情况下，这仍然可能是O（n^2）（例如，如果所有的点都在彼此的t之内），但它在某些情况下可能会有所帮助。

来源

2016-10-22 11:09:47

在二维空间中连接任意两点

回答

相关问题