2次元空間内の任意の2点を接続する

Question

O（n^2）より良いアルゴリズムがあれば、距離が定数tより小さい限り、任意の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以内にある場合など）でもかまいませんが、場合によっては役立ちます。