找到距离最远的点的算法 - 优于O(n ^ 2)？

Question

在我的计划中,我有一套积分.出于重新缩放的目的,我正在搜索最远的两个节点,然后计算乘以所有坐标的因子,使得最大距离等于我定义的某个预定义的距离.

然而,我用来找到最远的两个点的算法对于大的点集是有问题的,因为它是O(n^2); 伪代码(已经计算的距离被跳过):

 for each point in points:
     for each other point in points:
         if distance between point and other point > max
             max = distance between point and other point

有更快的东西吗？

Answer 1

如果您只需要比例而不是精确的点,您可以在O(n)时间内执行此操作并获得一些误差.想想制作边界框的简单案例.计算所有点的最小x值,最大x,最小y和最大y.这四个数字为您提供了围绕您的点的最大边界框,最大误差为1 - (1/sqrt(2))约30%.您可以通过在方块中添加更多边来减少此操作.想想八角形的情况.要计算其他边的最小值和最大值,必须旋转坐标系.

错误与运行时间分解如下.

形状 - 运行时间 - 最大误差

• 方块 - 2N - 30%
• 八角形 - 4N - 16%
• 16面 - 8N - 4%
• 32面 - 16N - 1%

这是我想出的最大误差的等式.

angle = 180 / sides
max_error = (1 / cos angle) - cos angle

如果我应该添加一个解释这个的图表,请告诉我.

Answer 2

以下可能有助于将平均情况线性时间算法(针对有限集的直径)放在更清晰的光线中,以及对比度多维和平面几何问题.

1983年,Megiddo为最小的封闭圆(或更高维度的球体)提供了确定性线性时间算法.

在一般位置,封闭圆在其边界上将具有两个或三个点,因此一旦知道了边界圆,就可以在恒定时间内"平均地"找到最远的两个点.在更高的维度中,球体边界上所需的一般位置上的点的数量增加(维度D的D + 1个点),并且实际上计算单个点对之间的距离的成本随着维度线性地增加.

位于边界圆或球面上的点子集也在线性时间内找到.在理论上最坏的情况下,所有点都位于边界圆或球面上,但这至少比在凸包上具有所有点更严格.如果球体上的点被独立地扰动,例如沿着径向线,则以概率1确保一般位置,并且可以从修改的封闭球体上的仅D + 1点找到近似直径.该随机化近似具有二维依赖于维度但仅具有点数的线性复杂度.

如果位于边界圆上的点被"排序"(当然是循环的),找到最远的对可以在线性时间内完成,依赖于圆的"单峰性"(意味着距离固定点的距离单调上升)直到antipode然后跌倒)来摊还计算距离的成本.不幸的是,排序将引入具有O(n log n)时间复杂度的步骤,并且这被证明是对于平面情况中的精确确定性方法的最坏情况最优.

2001年,Ramos成功地展示了用于三维集合的O(n log n)确定性算法,但该技术涉及到实施可能不实际或比蛮力全对搜索到非常大的数据集更慢.

对于更高维度,许多作者已经考虑了随机或近似算法.参见Piotr Indyk的论文(2000)的近似方法,其中只有多项式依赖于各种邻近问题的维数.

Answer 3

正如在这个答案中提到的,你正在寻找N点集的"直径",这是计算几何中众所周知的问题.基本上有两个步骤:

1. 找到点的凸包.存在的算法是O(N ln N),最坏的情况.实际上,QuickHull通常是一个快速选择,尽管可能是O(N ^ 2)最坏的情况.该QHull实现方便从命令行调用.CGAL库提供了C++实现

2. 凸壳上的对映对是最远点的候选对象.可以使用诸如在O(N)时间内旋转卡尺的算法搜索对映点.

这个问题可以归结为"所有最远的对"问题:对于每个点i,找到最远点j- 我们现在正在寻找N对点.解决方案再次使用凸包,但现在第二部分可以使用矩阵搜索算法完成.