- 248 名前：デフォルトの名無しさん mailto:sage [2005/12/18(日) 09:03:12 ]
- >>237
空間データベースって分野のお話だね．
望んだ形でデータを持ってていいなら，k-d tree を使うのが手軽かな．
空間に一点が追加されるたびに，その一点を通る超平面を引き，その超平面のどちら側に
点があるかで二分木を作る．探索は木を手繰りながら範囲を絞り込んで，
その中で全探索をする．最悪 O(n) だけど，適当にばらけてれば O(log n)．
ほかにも SR-tree とか SS-tree とか色々あるので，参考になりそうなのを挙げとく：
www.kecl.ntt.co.jp/csl/sirg/people/kani/db.html
vision.unige.ch/~moennen/publi/moennen_tech0505.pdf
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley
