短い中間ホップで到達可能な2D点を見つける

Question

2D点に対応する約60,000ノードのリストallNodesがあります。私は

for(i in allNodes) 
    for(j in allNodes) 
    if(distance(i, j) <= 10) addEdge between i and j 

のような隣接リストを構築し、その後sourceNodesから到達可能なノードのセットを見つけるために、sourceNodesのセットから深さ優先探索を行っています。これを2次式より速くするにはどうすればよいですか？私はC + +を使用しています。

Answer 1

David Eisenstatの答えが示唆するビニング手法は、データが指定したプロパティではない点が均等に分布していると思われる場合に機能します。さらに、前述のように、Delaunay triangulationは、指定された距離内のすべてのノードが確実に見つかるように誘導グラフ上でローカル検索を依然として必要とします。

保証されたパフォーマンスを得る1つの方法は、kd-treeです。 O（2n log n）時間で構築することができます（保証について気にしないでランダム化を使用しない場合は速くなります）。O（2n√n）。

Delaunay三角形分割やkd-treeが実際より高速かどうかは不明ですが、心配していると、適切なkd-treeライブラリを見つけて使用することが迅速かつ簡単な解決策になると思われます開発時間について

Answer 2

簡単なアプローチは、d> 10のビンにd-by-dを分け、各ポイントをフロア（x/d）、フロア（y/d）でインデックスされたビンに入れます。その後、代わりにポイントがうまく分散している場合、これはより速く、物事を行います

for bin1 in bins: 
    for i in bin1: 
     for bin2 in bins neighboring bin in nine directions (including bin): 
     for j in bin2: 
      if(distance(i, j) <= 10) addEdge between i and j 

ポイントのすべてのペアを、繰り返し処理が、最悪の場合は、まだ二次であるの。

O（n log n）時間アルゴリズムを保証するには、Delaunay三角測量を計算し、10より長いエッジを捨てます。これにより、距離が10以下のノード間の直接接続がいくつか削除されますが、依然として間接的に接続される。