[問題] 平面上 N 點，放額外一點 P 求最近點

[EdisonX (卡卡獸)]

變數假設

struct Point { float x , y ; }
Point a[m];
Point b[n];

最大點對 問題是在 a 裡面，找最近的兩點 ，
( ↑雖然這我也不會有效的方法  )
但我的問題是，把 a[i] 依序放入 b 中，
從 b 裡找出與 a[i] 最近的點，
暴力法用虛碼表示如下

for(i = 0 : m-1 )
{
   min_idx  = 0 ;
   min_dist = distance( a[i], b[min_idx] );

   for(j = 1 : n-1)
   {
       dist = distance( a[i] , b[j] ) ;
       if ( dist < min_dist)
       {
           min_dist = dist ;
           min_idx  = j;
       }
   }
   // min_dist , min_idx 是要求的 , 到時候會全部存下來
}

想請教是否有什麼算法可較快完成上述需求？
或我該找什麼 keyword ?
先謝謝各位。

--
 「自從我學了 C#   , 人都變聰明 , 考試都考一百分」
 「自從我學了 VB   , 皮膚都變好 , 人也變漂亮了  」
 「自從我學了 Java , 明顯變壯   , 個子也變高了  」
 「自從我學了 C++  , 內分泌失調 , 頭都禿了...   」
                                          < Kuso 星爺語錄 >

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1414674032.A.1D6.html
→ bibo9901: closest pair problem
這算法是找 b[n] 裡的最近兩點不是嗎？

但我想找的  "比較像 (但似乎不完全是)" 是，

給定一點 c , 求 c 與 b[n] 裡最近的一點，

還是這問題一樣可以從 最小點對 (closest pair) 問題轉過來？

謝謝您的回答。
※ 編輯: EdisonX (180.177.74.8), 10/30/2014 21:09:39
推 FRAXIS: nearest neighbor query
→ EdisonX: 疑！想一下也像是 knn(k==1) , 實作上似乎麻煩多 Orz
→ EdisonX: 謝謝 FRAXIS , 我再搜一下有什麼算法解這問題 , 感謝
推 m80126colin: 有個東西叫做 Voronoi Diagram，不知道有沒有相關？
→ scwg:  http://stackoverflow.com/questions/5077318/
→ scwg: 是你要的嗎? 還是你要 min_dist/idx forall a?
→ scwg: kd-tree for b should help anyway
→ EdisonX: @scwg , 嗯 , 我要的是 min_dist/idx forall a? , 謝謝
→ EdisonX: 提供的 keyword , 感謝。
今天抽時間稍試了下，kd-tree, 在 asize = bsize = 40M , dim==2 的情況下，
雖然比暴力法很好多，
似乎還是要花費不少時間 , 我試著去優化 code , 節省還是有限 .
不知道有沒有人對這議題有所研究可再提供點方向？
謝謝各位。
※ 編輯: EdisonX (180.177.74.8), 10/31/2014 21:28:35
→ LPH66: kd-tree 主要是查詢省時間, 點集固定查詢點很多時很有用
推 FRAXIS: 因為你的b是靜態的 先建Voronoi diagram
→ FRAXIS: 然後建立point location的查詢 應該會比較快
推 DJWS: scholar.google.com.tw/scholar?&q=nearest+neighbor+query
→ DJWS: books.google.com.tw/books?&q=nearest+neighbor+query
→ DJWS: 這個題目有成千上萬人做過  方向很多
→ DJWS: 比較淺顯易懂的介紹 http://www.cs.uu.nl/geobook/
→ EdisonX: 明天我整理下目前所做的 code 放上來 , 先謝謝各位給的
→ EdisonX: 資訊，真的非常感謝！
先說下吧，我用的是 http://rosettacode.org/wiki/K-d_tree
這網頁的 code 抓下來改，

整個順序如同 FRAXIS , LPH66 所言，一堆 b 事先做 make_tree 後，
再逐一將每個 a 點丟到 nearest 做查詢，
效能上是比暴力法提升了一百多倍，唯需求上盡可能還需再快，
想請教這效能是否已是上限？

若說明不夠，需再放我手上版本的 code , 我可再附上。
謝謝各位。
※ 編輯: EdisonX (180.177.74.8), 11/03/2014 23:55:21
推 FRAXIS: Kd-Tree是支援dynamic insert/delete的
→ FRAXIS: 你的問題中b是靜態的  所以要找static data structure