线性时间内的最小轴平行边界框

Question

问题
我必须在线性时间 O(n) 中计算一组二维点的直径。

为了做到这一点，我想到了使用可以在线性时间内计算的最小轴平行边界框，并从凸多边形开始旋转卡尺。
不幸的是，我没有凸多边形，由于凸包，计算它需要 O(nlogn) 时间。

我的想法是使用基数排序，然后通过单调链算法计算凸包（如果输入排序，则需要线性时间）。

现在我的问题是：

• 如何确定基数排序在线性时间内 运行？
• 你有更好的想法来计算线性时间内的最小轴平行边界框吗？

提前致谢！

编辑
我特别需要最小边界框，因为我必须为直径设计一个 sqrt(2) 近似算法，这是我知道的证明这个近似的唯一方法。

Answer 1

如果您正在寻找一组点的 直径 ，Welzl's algorithm 可能是您的最佳选择。它在线性时间内找到最小外接圆。

编辑：我没有意识到你需要做一个盒子。要找到最小边界框的轴对齐边界，您只需要对数据进行线性扫描并获取 (x,y)[= 的适当 min/max 值19=]坐标.