search - 具有恒定尺寸或三角形形状的凸包

Question

我知道 QuickHull 算法在 Theta(n) 中运行，如果凸包是三角形的或者它具有恒定的大小。

这是什么意思？

我不确定形状（如果它看起来是三角形），因为该算法使用 4 个极值点。

谢谢

Answer 1

如果凸包的顶点数 letH是一个常数（不依赖于N），那么 QuickHull 花费的时间与N（更准确地说c1.N < T < c2.N是两个常数c1和c2）成正比。

当 时H=3，船体为三角形。不管算法如何工作，它都必须返回这个三角形。仔细的实现甚至应该适用于H=2（线段）或H=1（单点）。