メモ書き. 全探索 (線形探索) 最も単純な方法は全探索である.注目点から空間中の全点の距離を測り, その距離が最小になる点を最近傍点とする.なお,計算量はO(n) k-d tree (k-dimensional tree) 上手に二分木をつくることで探索空間を二分探索することが可能.最も有名なのがk-d tree. どうやって木をつくるか 簡単のため2次元で考えると手順は以下のようになる. 1. x軸に平行(別に垂直でもよい)に空間を二分割する.上下でノードをつくる 2. y軸に平行に空間を二分割する.左右でノードをつくる 3. x軸に平行に空間を二分割する.上下でノードをつくる 4. ・・・ これを再帰的に繰り返す. 分割とk-d tree どうやって空間を二分割するか 図では簡単のために単純にど真ん中で空間を分割しているが, 点の座標値の中央値で分割するとk-d treeは平衡木にな