如果两点间的距离小于一个常量t，有没有比O(n^2)更好的算法将这两个点用一条直线连接起来？
我在考虑按照它们的x坐标对点进行排序，然后在[x-t,x+t]范围内寻找另一个点。但最坏情况仍为O(n^2)。有什么想法吗？我们有任何特殊的数据结构可以加速吗？
在二维空间中连接任意两点
3
- crucialoil
3
2搜索“最近点对问题”。 - n. m.
是否存在t的限制？否则，如果所有点之间的距离都在t以内，则必须将每个点与每个其他点连接起来，这总是O(n^2)。 - TilmannZ
此外，搜索“空间连接”，例如TOUCH算法可以找到所有距离最大的点对。但是，如果您使用一个好的通用多维索引（如果需要我可以推荐一个），也可以实现类似的性能。 - TilmannZ
1个回答
2
有一种可能会有所帮助的方法是对于每个点计算一个bucket，具体如下：
int(x/t),int(y/t)
将点（0.1，0.9）、（0.5，0.5）、（0.8，0.2）放入同一个桶中。
将所有点放入这些桶中，然后再次迭代点。
这种组织方式的原因是您只需要检查点与同一桶中的点或相邻8个桶中的点。
在最坏情况下，仍可能达到O（n ^ 2）（例如，如果所有点都在t之内），但在某些情况下可能会有所帮助。
- Peter de Rivaz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接