matlab - QuickHull 最坏情况

Question

QHull（也许还有其他很好的QuickHull实现）在许多情况下运行得非常好而且很快。然而，理论上我们知道它的最坏情况可能是 O(n^2)。在实践中，我没有看到任何具有多维（即 20 或 100）的数值示例，其中 QHull 效果不佳。

您是否知道 QHull 工作不佳或给出错误结果的数值示例，或者任何表明它不能在这里应用的例子。

Answer 1

对于多维情况，您必须概括 A. Donda 所说的：为 P 中的每个点 p 生成一组具有 norm(p)==1 的点 P。凸包是 P（除非两个点相同）并且将导致~O(n^2) 的糟糕运行时间

对于 2D 案例，这将选择圆上的点，对于球体上的 3D 点。