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