动态凸包技巧

Question

我在空闲时间阅读了有趣的算法，我刚刚发现了凸包技巧算法，我们可以使用该算法计算给定x坐标中平面上几行的最大值。我发现这篇文章：

http://wcipeg.com/wiki/Convex_hull_trick

笔者在这里说，该算法的动态版本在对数时间运行，但没有证据。当我们插入一条线时，我们测试了他的一些邻居，但我不明白如何通过这样的插入来测试所有的N行时它怎么可能是O(log N)。这是正确的还是我错过了什么？
UPDATE：这个问题已经回答了，将有趣的是下面

• 其余部分，我们如何删除？
  我的意思是......如果我们删除一条线，我们可能需要先前的线来重置整个船体，但是当插入一个新的线时，该算法将删除所有不必要的线。
• 它是一个另一种方法，来解决类似上述问题（或类似的，例如像管理查询插入，删除，在X点或在给定范围等找到最大）

谢谢提前！

Answer 1

要回答你的第一个问题：“如何插入O（logn）？”，你最终可能会检查O（n）邻居，但请注意，当你发现你只需要检查一个额外的邻居需要做一个删除操作。

问题是，如果您要插入n个新行，那么您最多可以执行n次删除操作。因此，除了需要在排序的数据结构中查找其位置所需的O（logn）每行工作外，额外工作的总数至多为O（n）。因此，插入所有n行的总工作量为O（n）+ O（nlogn）= O（nlogn），换句话说，每行分摊O（logn）。

Answer 2

1. 摊销的制品的权利要求（而不是最坏情况）每次插入O(log N)时间。缓冲区限制很容易证明（每行最多删除一次，每次检查都是最后一行或导致删除一行）。

2. 这篇文章并没有说这个数据结构完全支持删除。我不确定是否有可能有效地处理它们。有一个障碍：时间复杂性分析是基于这样一个事实：如果我们删除一条线，我们将来将永远不需要它，但在允许删除时情况并非如此。

Answer 3

插入可以比O（log n）更快，它可以在O（Log h）中实现，其中h是已经计算的Hull点的集合。可以在每个点的O（log h）中进行批量插入或逐个插入。你可以阅读我的文章有关：

1. A Convex Hull Algorithm and its implementation in O(n log h)
2. Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
3. First and Extremely fast Online 2D Convex Hull Algorithm in O(Log h) per point

关于删除：我敢肯定，但它必须证明，它可以实现在O（log n + log h）= O（log n）每点。关于它的文本可以在我的第三篇文章结尾处找到。