我有一个大约100,000(X,Y)对的数据集,代表2D空间中的点.对于每一点,我想找到它的k-最近邻居.
所以,我的问题是 - 假设我想绝对最小化整体运行时间,那么什么数据结构/算法将是一个合适的选择？
我不是在寻找代码 - 只是指向合适方法的指针.我有点害怕看似相关的选择 - 四棵树,R树,kd树等.
我认为最好的方法是构建一个数据结构,然后为每个点运行某种k-Nearest Neighbor搜索.但是,由于(a)我事先知道了这些要点,并且(b)我知道我必须对每个点进行一次搜索,或许有更好的方法？
一些额外的细节:
您将获得平面中的点列表,编写一个程序,输出每个点以及最接近它的其他三个点.这三点按距离排序.
例如,给定一组点,其中每一行的形式为:ID x坐标y坐标
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
你的程序应该输出:
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1
这是我在在线论坛上发现的一个面试问题.我可以想到一个O(n*n)解决方案:计算每个点到每个其他点的距离.返回此点的最小距离点.对其他点重复此过程