computational-geometry - quadtreeとkd-treeの違い

Question

quadtree と kd-tree の主な違いは何ですか? ポイントが多くの次元で分割されていることは理解していますが、なぜ一方を他方に使用するのかわかりません。特定の領域にあるポイント (2D ポイント) の数をカウントできる構造が必要です。基本的に、ポイントのクラスターを検出しようとしています。

Answer 1

違いは（アルゴリズム的に）次のとおりです。クアッドツリーでは、ノードに到達するデータは固定（2 ^ d）の等しいサイズのセルに分割されますが、kdtreeでは、データはデータ分析に基づいて2つの領域に分割されます（中央値など）。いくつかの座標の）。四分木は、次元の指数関数的な依存関係のため、高次元にうまくスケーリングしません。データ構造は、クエリ時間の複雑さも異なります。

2Dポイントに関心があるので、どちらのデータ構造でも機能する可能性があります。KDツリーは範囲のクエリが非常に簡単で、通常はクワッドツリーよりも優先されます。それらを使用することをお勧めします。