QuickHull最坏情况

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

你知道一个数值例子，其中QHull工作得不好，或者给出了错误的结果，或者任何表明它不能在这里应用的数值例子。

2013-12-07 Alef

你的意思是“很多数据点”，对吧？ AFAIK quickhull仅适用于二维数据。 - 根据维基百科，最坏的情况是O（n²），O（n log n）是平均值。 –

维基百科：“在高对称性或点位于圆周上的情况下，处理通常会变慢” –

无论哪种方式，许多数据点和/或许多维度。其实这是正确的，最坏的情况是O（n^2）。谢谢。我编辑了这个问题。 – Alef

对于多维情况，您必须推广A. Donda所说的内容：对于P中的每个Point p，生成一个带有范数（p）== 1的Point P的集合。凸包是P（除非两个点完全相同）并且会导致运行时间很短〜O（n^2）

对于2D Case，这将选择一个圆上的点，以表示球上的3D点。

2013-12-07 18:43:59 Daniel

回答