次线性但简单的动态凸包算法？
我需要解决动态凸包算法问题，即维护二维点的凸包，我可以在其中添加和删除点。
简单的方法显然是O(N)；每当添加/删除 N 个点之一时，我们都会从头开始重新计算凸包。然而，我无法承担线性时间，所以我正在寻找一种次线性算法。到目前为止，我发现了一堆论文，所有这些论文都描述了一些具有疯狂时间限制的复杂算法，这需要很长时间才能实现。即使是由 Overmars 和 Leeuween 提出的最古老的高效算法，其 O(log^2 N) 似乎也太复杂了。 （像往常一样，此类论文中描述的大多数算法在结构/算法方面与其他参考论文有大量的依赖性）
我正在寻找更简单的东西，不一定是新颖的，在最坏的情况下它的性能比线性的更好（例如O(sqrt N)）。最后，我不介意时间是否摊销。有什么想法吗？
（简单地说，我主要指的是不需要超过几百行代码的东西。）
I need to solve dynamic convex hull algorithm problem, i.e. maintaining the convex hull of 2D points, where I can add and delete points.
The naive approach is clearly O(N); whenever one of the N points is added/deleted, we recompute the convex hull from scratch. However, I cannot afford linear time, so I am looking for a sublinear algorithm. So far, I have found a bunch of paper all of which describe some sophisticated algorithm with crazy time bounds which would take ages to implement. Even the oldest efficient algorithm, due to Overmars and Leeuween, which is O(log^2 N) seems way too complicated. (As usual, most of algorithms described in such papers have tons of dependencies in terms of structures/algorithms from other, referenced papers)
I am looking for something simpler, not necessarily novel, which performs better than linear in the worst case (e.g. O(sqrt N)). Finally, I don't mind if the time is amortized. Any ideas?
(By simple, I primarily mean something that does not require more than a few hundred lines of code.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为你所寻求的并不存在。 Overmars 和 vanLeeuwen 算法并没有那么复杂，而且在某种意义上似乎是必要的。首先，将问题改为上船体和下船体分别维护。其次，通过分治法构造每个点，但保留中间树结构，以便您知道 1/2 集、1/4 集等的外壳。现在，当您删除一个点时，您仅重新计算树中的祖先。当您添加一个点时，您会找出它连接到哪个叶子，并再次向上重新计算到根。
我认为，如果你忽略他们论文中的细节，只是遵循这个高级草图，并以最无意识的方式实现所有步骤，它不会很复杂，而且会是次线性的。
MH Overmars 和 J. van Leeuwen。
飞机配置的维护。
J.计算。系统。科学，23：166-204，1981。
I think what you seek does not exist. The Overmars and vanLeeuwen algorithm is not that complicated, and it seems in some sense necessary. First, change the problem to maintaining the upper hull and the lower hull separately. Second, construct each by divide-and-conquer, but retain the intermediate tree structures, so that you know the hulls of the 1/2-sets, the 1/4-sets, etc. Now, when you delete a point, you recompute only its ancestors in the tree. When you add a point, you find out to which leaf it joins, and again recomputed upwards to the root.
I think if you ignore the details in their paper, and just follow this high-level sketch, and implement all the steps in the most mindless manner, it will not be complicated, and will be sublinear.
M. H. Overmars and J. van Leeuwen.
Maintenance of configurations in the plane.
J. Comput. Syst. Sci., 23:166-204, 1981.
对于 O'Rourke 教授，他对计算几何的了解远比我多，我不认为 OvL 的“无意识”实现（即缺乏重新平衡）在最坏的情况下可能是次线性的。案例。
幸运的是，自 1981 年以来，我们在数据结构方面取得了一些进展。特别是，由于摊销保证就足够了，因此展开树（1985）适合存储凸包和合并树。 奥斯特恩等人。 (2003) 提出了一种很好的方法，将需要的额外字段的维护与复杂的平衡操作分开，这样您就可以一次性编写棘手的部分。
实现展开树的主要困难是展开操作，即使这样也比插入红黑树要简单得多。一旦展开工作，展开树就可以轻松地进行分割和连接。要拆分，请展开要拆分的节点并剪切其右子节点。要加入，请展开第一棵树的最右侧节点，并使第二棵树成为该节点的右子节点。
With respect to Prof. O'Rourke, who knows far more than I ever will about computational geometry, I don't see how a "mindless" implementation of OvL (i.e., one lacking rebalancing) could be sublinear in the worst case.
Fortunately, we've made some advances in data structures since 1981. In particular, since an amortized guarantee is enough, splay trees (1985) are appropriate for storing both convex hulls and the merge tree. Austern et al. (2003) proposed a nice way to separate the maintenance of the extra fields that will be required from the complex balancing operations, so you can write the tricky parts once.
The main difficulty in implementing splay trees is the splay operation, and even that is much simpler than, say, inserting into a red-black tree. Once splay works, splay trees are easy to split and join. To split, splay the node you want to split after and cut its right child. To join, splay the rightmost node of the first tree and make the second tree the right child of that node.
我假设总共有 N 个数据点，复杂的船体由 M 个点定义。
维护凸包应该比最初构建它更容易（而且更便宜）。
删除现有数据点
添加新数据点。
这是一个简单的方法来测试我的想法。创建船体内部的三角剖分。使用 M 个点定义的复杂外壳可以三角剖分为 M-2 个三角形。然后测试该点是否位于其中一个三角形内。
我不明白这些维护怎么可能是 O(N)
I am assuming that there are N data points in total and the complex hull is defined by M points.
It should be far easier (and less expensive) to maintain a Convex Hull than to build it in the first place.
Removing an existing data point
Adding a new data point.
Here is a simple way to test this off the top of my head. Create a triangulation of the interior of the hull. A complex hull defined using M points can be triangulated into M-2 triangles. Then test if the point lies in one of the triangles.
I don’t see how any of this maintenance can be O(N)