QuickHull最坏的情况

Question

QHull（也许还有QuickHull的其他好的实现）在许多情况下都能很好地快速工作。然而，我们从理论上知道，它的最坏情况可以是O（n^2）。在实践中，我没有看到任何具有许多维度（即20或100）的QHull工作不佳的数值示例。

你知道QHull工作不好的数字例子吗，或者给出了错误的结果，或者任何表明它不能在这里应用的东西。

Answer 1

对于多维情况，你必须推广A.Donda所说的：为p中的每个点p生成一组范数（p）==1的点p。凸包是p（除非两个点相同），并将导致~O（n^2）的坏运行时间

对于二维情况，这将选择圆上的点，对于球体上的三维点。