計算アルゴリズム【Ⅱ】

計算アルゴリズム【Ⅱ】 at TECH

248:デフォルトの名無しさん
05/12/18 09:03:12
>>237
空間データベースって分野のお話だね．

望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな．
空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に
点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで，
その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)．

ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく：
URLﾘﾝｸ(www.kecl.ntt.co.jp)
URLﾘﾝｸ(vision.unige.ch)
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley

次ページ

続きを表示

1を表示