2

当输入中的所有点都位于凸包上时，如何避免快速壳算法的性能不佳？

4

2 回答 2

2

QuickHull 的性能主要来自能够在每次递归调用（或迭代）时丢弃一部分输入。不幸的是，当所有点都在一个圆上时，这不会发生。即使在这种情况下，如果拆分步骤在每次递归调用时都提供了相当平衡的分区，仍然可以获得O(nlog n)的最坏情况性能。导致二次运行时的最坏情况是我们在每次调用中都有严重不平衡的分割（比如一个分割总是以空的结尾）。因为这在很大程度上取决于数据集，所以对此无能为力。

您可能想尝试其他算法，例如Andrew 的 Graham 的 scan 变体或MergeHull。两者都保证了O(nlog n)最坏情况的时间复杂度。

于 2012-05-05T07:32:26.810 回答
0

对于一些算法实现比较，我建议看我的文章：Fast and Improvement 2D Convex Hull algorithm and its implementation in O(n log h)比较许多 2D 算法的性能，如：

  • 单调链
  • 格雷厄姆扫描
  • 德劳内/沃罗诺伊
  • 陈
  • 刘和陈
  • 欧莱（我的）
于 2018-01-26T04:43:47.660 回答