algorithm - 線に近いポイントをすばやく検索する方法

Question

2D 空間に一連の点と線があります。直線から距離 D 以内にあるすべての点を見つける必要があります。線からすべての点の距離 di を実際に計算することなく、これを行う方法はありますか? 線形検索よりも優れたソリューションはありますか?

編集: 異なる行に対して同じポイント セットを複数回検索する必要があります。ポイントは常に一定ですが、線は検索ごとに異なります。通常、ポイント セットは数万 (~50k) のオーダーです。

Answer 1

クエリについて：

ポイントを使用して kd ツリーを作成し、ライン上のいくつかの等距離ポイント (おそらく d 付近) を使用する場合、変更された最近傍クエリを使用して、ラインから d 以内にあるすべてのポイントを大まかに見つけることができるはずです。 O(k + log(N))。kd-tree には O(N log N) の前処理が必要なので、同じポイント セットを使用する場合にのみ最適です (O(log N) で kd-tree からポイントを追加/削除できるため、おそらくわずかな違いがあります)。と異なる行。唯一の問題は、kd-tree が実際には行での使用を意図していないことです。よりうまく機能するラインにはそのようなものがあると確信していますが、私はそれに慣れていません。

注: ライン上の距離ではなく、ライン上のポイントからの距離を実際にクエリしているため、配置方法によっては、誤検知や誤検知が発生する可能性があります。これがどの程度問題になるかは、線の長さと d の比率に大きく依存します。したがって、ポイントの大部分が線の近くにない場合を除き、かなりの数の偽陽性または偽陰性が得られます。一般に、これはおそらくあまり問題にはなりませんが、偽陽性であっても、d が比較的大きくない限り、k は N に比べてかなり小さいはずです。

少し見直した後、クエリが線分ではなく線分に対するものであることに気付きました。ただし、最小/最大 x/y で囲まれた線分を作成することで、1 つに変換できます。これには、おそらく kd-tree を使用するより効率的な方法がまだあると思います。

Answer 2

入力データと結果の母集団の複雑さは同じであるため、この検索は線形検索よりも速く完了することはできません。