[解決済み] KD-treeとR-treeの違いは何ですか？

質問

KD-treeとR-treeの定義を見てみました。ほぼ同じだと思われます。

KD-treeとR-treeの違いは何ですか？

どのように解決するのですか？

R-木 と k d-ツリー は似たようなアイデア（軸に沿った領域に基づく空間分割）に基づいていますが、主な違いは以下の通りです。

• のノードが k d-treeは分離面を表し、R-treeのノードはバウンディングボックスを表します。
• k d-treeは空間全体を領域に分割するのに対し、R-treeは注目点を含む空間の部分集合を分割するだけです。
• k d-treeはdisjoint partition（点が1つの領域にのみ属する）を表すのに対し、R-treeの領域は重なる可能性があります。

(空間を分割するための木構造は、4分木、BSP-木、R*-木など、似たようなものがたくさんあります。）