空間分割
空間分割
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/13 07:55 UTC 版)
1970年代から、この問題に分枝限定法が適用されるようになった。ユークリッド空間の場合、この手法は空間索引または空間アクセス法として知られている。NNS問題を解くための空間分割法もいくつか考案された。最も単純な手法としてはkd木がある。これは、探索空間を再帰的に半分に2分割していくものである。クエリは、この木を根から葉に向かって辿っていくことで処理される（各ノードでどちらに行くかをクエリの内容と比較して判断する）。一定次元でのクエリ処理時間は O(log N) となる。R木というデータ構造も最近傍探索用に設計された。 一般の距離空間における分枝限定法の適用例として、VP木やBk木がある。
※この「空間分割」の解説は、「最近傍探索」の解説の一部です。
「空間分割」を含む「最近傍探索」の記事については、「最近傍探索」の概要を参照ください。
ウィキペディア小見出し辞書の「空間分割」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 空間分割のページへのリンク
