在二維空間中連接任意兩點

Question

只要距離小於常數t，是否有任何算法比O（n^2）更好地通過直線連接任意兩點？

我在考慮根據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之內），但它在某些情況下可能會有所幫助。