3 algorithm geometry
我有一组2D点,需要找到最快的方法来确定哪一对点在集合中具有最短距离.
这样做的最佳方法是什么？我的方法是用快速排序对它们进行排序,然后计算距离.这将是O(nlogn + n)= O(nlogn).
是否有可能在线性时间内完成？
谢谢.
lei*_*eiz 11
它实际上是:
在最近对点的问题或最接近对问题是一个问题,计算几何:给予ñ点度量空间,找到一个对点与它们之间的最小距离... 在假定floor函数可以在恒定时间内计算的计算模型中,可以在O(n log log n)时间内解决问题.如果我们允许随机化与floor函数一起使用,那么问题可以在O(n)时间内解决.
在最近对点的问题或最接近对问题是一个问题,计算几何:给予ñ点度量空间,找到一个对点与它们之间的最小距离...
在假定floor函数可以在恒定时间内计算的计算模型中,可以在O(n log log n)时间内解决问题.如果我们允许随机化与floor函数一起使用,那么问题可以在O(n)时间内解决.
归档时间：
16 年，7 月 前
查看次数：
10901 次
最近记录：
9 年，2 月 前