怎样快速求出离当前位置最近的点？
已知r维空间中某点集S，怎样快速求出离当前位置最近的点？
最简单的算法就是枚举点集S，逐个逐个与当前位置进行比较，最后输出距离最近的那个点。该算法复杂度为O(n)，若点集S有上百万个点，那么查询速度将会很慢。
主要是需要解决2维、3维空间中的最近点查询问题，如果有高维空间算法就更好。主要问题类型：
1.二维平直空间。最简单的模型。
2.二维曲面空面。比如在地图上查找最近的地理标注。一般地理标注的数量极大，至少上百万，可以用于验证算法对大规模数据的效率。
3.三维平直空间。比如色彩量化，匹配与当前颜色最接近的调色板颜色。调色板颜色条目数一般为256，可以用于验证算法对小规模数据的效率。
点集S是固定的，不需要考虑动态添加、删除问题。一般将点集S的数据放在普通的关系型数据库中。
[解决办法]
感觉可以用一个索引空间来做。例如在二维空间内，先将之分为10x10的格子，在插入每一个点的时候，同时记录它所在的格子索引。这样在判断最近位置的时候，只在最近的格子里面找点就可以了。当然格子根据大小不同也会多少占些内存的，有个取舍问题。
[解决办法]
我平时在处理大量2维点的时候也是将点分到很多小方格中。
和ls的思想一样。
其他的就不清楚了
[解决办法]
加个索引应该是比较好的方法，如果没有任何参考信息的话，就只能一个一个排除了，能改进的只有排除算法
[解决办法]
如果点的分布比较平均，而且之前没有划分区域的话，可以考虑人为的添加一个区域，比如二维空间之中，以指定点为中心建立一个合适大小的正方形，然后选择所有在这个正方形内的点，然后计算比较距离
[解决办法]
说掉了一点...最后的结果与指定点的距离应该不大于正方形边长的一半，否则应该扩大正方形重新寻找
[解决办法]
对于2维的情形，有经典的分治算法。
对于3维的情形，还是可以用分治法来设计算法。
有一篇论文就是关于这个的：
http://d.download.csdn.net/down/263756/medie2005
