Tim*_*oad 6 algorithm computational-geometry
您将获得平面中的点列表,编写一个程序,输出每个点以及最接近它的其他三个点.这三点按距离排序.
例如,给定一组点,其中每一行的形式为: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)解决方案:计算每个点到每个其他点的距离.返回此点的最小距离点.对其他点重复此过程
您可能需要研究 kd 树或四叉树等空间数据结构，它们为最近邻搜索提供了出色的预期时间保证。例如，在进行 O(n log n) 预处理工作后，kd 树可以在 O(n) 最坏情况时间和 O(sqrt N) 预期时间内进行最近邻搜索。
或者，如果您知道这些点大部分是随机分布的，您可以考虑将空间划分为某个固定大小的桶的集合。要找到一个点的最近邻居，您可以查看同一个存储桶中的所有点，然后查看附近存储桶中的所有点，等等。如果这些点很好的话，每个点的时间应该接近 O(n / b)分布式，有b个桶。
希望这可以帮助！