代码之家 › 专栏 › 技术社区 › Benny

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

radix-sort convex-hull bounding-box algorithm

1

Benny · 技术社区 · 8 年前

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

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

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

现在我的问题是:

提前感谢您!

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

1 回复 | 直到 8 年前

1

2

Richard 8 年前

如果你正在寻找直径一组点的, Welzl's algorithm 可能是你最好的选择。它可以在线性时间内找到最小包围圈。

编辑 :我不认识你需要制作一个盒子。要查找最小边界框的轴对齐边界,只需对数据进行线性扫描,并获取适当的最小/最大值 (x,y) 协调。