用快速船体算法计算凸包

2 回答

• 1

  我猜QuickHull的最坏情况是当没有发生拒绝时，即当给定点形成凸多边形时，以及当分区是最不 balancer 的时 .

  因此，您可以沿着圆取点，角度在几何上逐渐减小 .

  

  回复于 2024-05-03T07:04:05+08:00
• 1

  构造一组可以生成最坏情况时间复杂度行为的点取决于您正在研究的材料中给出的特定伪代码 .

  Quickhull的最坏情况复杂性为 O(N2) ，平均案例性能为 O(NlogN) . 正如您所看到的，Quickhull遵循分而治之的策略 . 因此，实现后者（即更好的）时间复杂性取决于能够将问题分成2个相似大小（理想情况下相等）的子问题 . 如果分割步骤不 balancer ，并且2个子问题中的元素数量差别很大，则算法必须递归N次 . 换句话说，在每个递归步骤中，问题大小将减少一个恒定的量，而不是减少到原始问题大小的一小部分 .

  现在，您提供的伪代码将具有最低和最高X坐标（即最左侧和最右侧点）的点作为边界将空间划分为两个 . 理想情况下，这应该将点分成2个同样大的集合 . 但是，如果通过输入的特定点使这种方法效率低下怎么办？然后，在每个步骤中，您可能只排除一定数量的点，比如 c ，而另一半仍然包括 N-c 点 . 因此，问题必须逐步减少_487764_步骤并最终导致二次复杂度 .

  我相信，其中一个例子就是用点绘制V形，如下所示 .

  (0, 5)
  (10, 5)
  (1, 4)
  (9, 4)
  (2, 3)
  (8, 3)
  (3, 2)
  (7, 2)
  (4, 1)
  (6, 1)
  (5, 0)
  

  回复于 2024-05-03T07:04:05+08:00