从凸包中删除最左边的点

Question

我有一组 N 2d 点，按 x 坐标和该组的上凸包排序。在从集合中删除最左边的点或在右边插入新点后，我正在尝试更新当前的凸包。

使用二分搜索可以在 O(logN) 内完成插入。

删除出现问题。让我们举一个最坏情况的例子。假设我们有一组黑点并删除红点。之后凸包应该被完全更新。这导致时间复杂度为 O(N)。

有没有什么算法可以支持从左边删除不超过O(logN)？

Answer 1

这属于一类称为“动态凸包问题”的问题——在插入、删除或修改节点等离散变化下维护凸包。

正如您的示例所示，删除单个顶点可以将凸包从三角形更改为包含所有剩余点的凸包。在这种情况下，输出是线性的。复杂度不可能比输出更好，所以复杂度最多是 O(n)。