我需要解决动态凸包算法问题，即维护2D点的凸包，我可以在其中添加和删除点。
天真的方法很明显O(N)；每当N添加/删除其中一个点时，我们都会从头开始重新计算凸包。但是，我负担不起线性时间，所以我正在寻找一种次线性算法。到目前为止，我找到了一堆论文，所有这些论文都描述了一些复杂的算法，这些算法具有疯狂的时间界限，需要很长时间才能实现。即使是最古老的高效算法，由于 Overmars 和 Leeuween，这O(log^2 N)似乎也太复杂了。（像往常一样，此类论文中描述的大多数算法在结构/算法方面与其他参考论文有大量依赖关系）
我正在寻找更简单但不一定新颖的东西，它在最坏的情况下比线性表现更好（例如O(sqrt N)）。最后，我不介意时间是否摊销。有任何想法吗？
（简单来说，我主要是指不需要超过几百行代码的东西。）
我认为你所寻求的并不存在。Overmars 和 vanLeeuwen 算法并没有那么复杂，在某种意义上它似乎是必要的。首先，将问题改为分别维护上船体和下船体。其次，通过分而治之的方式构造每个，但保留中间树结构，以便您知道 1/2-sets、1/4-sets 等的外壳。现在，当您删除一个点时，您仅重新计算其在树中的祖先。当您添加一个点时，您会发现它连接到哪个叶子，并再次向上重新计算到根。
我认为如果你忽略他们论文中的细节，只按照这个高级草图，以最无脑的方式实现所有步骤，它不会复杂，而且会亚线性。
MH Overmars 和 J. van Leeuwen。维护飞机中的配置。 J.计算机。系统。科学。, 23:166-204, 1981。
关于 O'Rourke 教授，他对计算几何的了解比我以往任何时候都多，我看不出在最坏的情况下，OvL 的“无意识”实现（即缺乏再平衡）如何可能是亚线性的。
幸运的是，自 1981 年以来，我们在数据结构方面取得了一些进展。特别是，由于摊销保证就足够了，splay trees (1985) 适用于存储凸包和合并树。奥斯特恩等人。(2003)提出了一种很好的方法，可以将需要的额外字段的维护与复杂的平衡操作分开，这样您就可以编写一次棘手的部分。
实现展开树的主要困难是展开操作，甚至比插入红黑树要简单得多。一旦展开工作，展开树很容易分裂和加入。要拆分，请张开要拆分的节点并剪切其右子节点。要加入，展开第一棵树的最右边的节点并使第二棵树成为该节点的右子节点。
我假设总共有 N 个数据点，复杂的外壳由 M 个点定义。
维护 Convex Hull 应该比一开始就建造它要容易得多（而且成本更低）。
删除现有数据点
1/ If the data point in not one of the M points defining the convex hull then it won’t affect the hull so just remove it.
2/ If it is part of the convex hull then you need to adjust the hull – more on that below in point 4
添加一个新的数据点。
3/ If a data point is inside the complex hull then it will not affect the hull.
这是一个简单的方法来测试我的头脑。创建船体内部的三角剖分。使用 M 个点定义的复杂船体可以三角剖分为 M-2 个三角形。然后测试该点是否位于三角形之一。
4/ if a data point is outside the hull then it will become part of the hull. However, it is only affecting a local area of the hull and it is straightforward to find the new hull in a few steps. If you have already build the hull then it should be clear to you how to adjust a local part of it.
我看不出这种维护怎么可能是 O(N)