algorithm - 如何在O(n^2)时间内实现在线构造Convex Hull？

Question

在线构造，一个一个地获取输入点，并为到那时为止给定的点找到船体。

我可以在 O(n * nlogn) 或 O(n^2 logn) 中使用 Graham 扫描来做到这一点。但我正在寻找一个 O(n^2) 解决方案。

我读过 Melkman 的O(n) 算法。这是正确的方法吗？

Answer 1

这可以使用 Graham 扫描的轻微修改来完成。回想一下，静态凸包的格雷厄姆扫描仅需要 O(N lg N)，因为需要在开始时按角度对点进行排序。之后实际的堆栈操作只需要 O(N)。

因此，我们维护一个链表，其中包含我们维护的所有点，按角度排序。每个额外的点都可以在 O(N) 时间内插入到正确的位置。之后，Graham 的栈操作部分仍然可以在 O(N) 时间内完成。

因此，由于有 N 次插入，每次插入的工作量为 O(N)，因此打印所有增量凸包需要 O(N^2) 的时间。