quadtreeとkd-treeの違い

Question

quadtreeとkd-treeの主な違いは何ですか？私は彼らが多くの次元でポイントを分割することを理解していますが、私はなぜそれを使用するのか理解していません。 与えられた領域にいくつの点（2D点）があるのか​​を数えることができる構造が必要です。 基本的に、私はポイントのクラスタを検出しようとしています。

Answer 1

違い（アルゴリズム的に）：四分の一で、ノードに到達するデータは、固定された（2^d）の等しいサイズのセルに分割されますが、kdtreesでは、データがいくつかのデータ分析（例えば、ある座標の中央値）。次元の指数関数的依存性のため、四分木は高次元にうまく適合しません。データ構造もクエリ時間の複雑さが異なります。

2Dポイントに興味がありますので、いずれのデータ構造でも動作します。 KDツリーは、範囲を照会するのが非常に簡単であり、一般にクォードツリーよりも好ましい。私はそれらを使用することをお勧めします。