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 点。