变量假设
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 ?
先谢谢各位。

closest pair problem

nearest neighbor query

疑！想一下也像是 knn(k==1) , 实作上似乎麻烦多 Orz谢谢 FRAXIS , 我再搜一下有什么算法解这问题 , 感谢

有个东西叫做 Voronoi Diagram，不知道有没有相关？

http://stackoverflow.com/questions/5077318/是你要的吗? 还是你要 min_dist/idx forall a?kd-tree for b should help anyway

@scwg , 嗯 , 我要的是 min_dist/idx forall a? , 谢谢提供的 keyword , 感谢。

kd-tree 主要是查询省时间, 点集固定查询点很多时很有用

因为你的b是静态的 先建Voronoi diagram然后建立point location的查询 应该会比较快

scholar.google.com.tw/scholar?&q=nearest+neighbor+querybooks.google.com.tw/books?&q=nearest+neighbor+query这个题目有成千上万人做过 方向很多比较浅显易懂的介绍 http://www.cs.uu.nl/geobook/

明天我整理下目前所做的 code 放上来 , 先谢谢各位给的资讯，真的非常感谢！

Kd-Tree是支援dynamic insert/delete的你的问题中b是静态的 所以要找static data structure