次线性但简单的动态凸包算法？

Question

我需要解决动态凸包算法问题，即维护二维点的凸壳，其中可以添加和删除点。

朴素的方法显然是O(N);每当添加/删除N个点之一时，我们就从头开始重新计算凸壳。然而，我无法承受线性时间，因此我正在寻找一个次线性算法。到目前为止，我已经找到了一堆论文，所有这些论文都描述了一些具有疯狂时间界限的复杂算法，这些算法要实现将需要很长时间。即使是最古老的高效算法，由Overmars和Leeuween提出的，其时间复杂度为O(log^2N)，似乎也过于复杂。（通常情况下，这些论文中描述的大多数算法在结构/算法方面都引用了其他参考论文中的大量依赖项）

我正在寻找更简单的东西，不一定是新奇的，但在最坏情况下表现得比线性好（例如O(sqrt N)）。最后，如果时间是平摊的，也没有关系。有什么想法吗？

（通过简单，我主要是指不需要超过几百行代码的东西。）

- eold

---

我不认为线性复杂度解决方案是幼稚的，因为在线性时间内找到 N 个点的凸包是幼稚的。实际上，我不知道有什么算法可以在线性时间内解决这个问题，即使对于单个集合也是如此。 - Ivaylo Strandjev

izo 是正确的：在最常见的计算模型下，存在一个 Omega(n log n) 的时间复杂度下限。 - Joseph O'Rourke

“O(N)”指的是每个操作的成本。天真的方法是保持点排序，并在每个步骤（删除/插入后）以“O(N)”的时间复杂度执行Graham扫描。 - eold

Answer 1

我认为您所寻找的内容并不存在。Overmars和vanLeeuwen算法并不那么复杂，从某种意义上说似乎是必要的。首先，将问题转化为分别维护上下凸壳。其次，通过分治构造每个凸壳，但保留中间树结构，以便您知道1/2集合、1/4集合等的凸壳。现在，当您删除一个点时，只需重新计算它在树中的祖先。当您添加一个点时，找出它加入到哪个叶子，并再次向上重新计算到根。

我认为，如果您忽略他们论文中的细节，只按照这个高层次的草图进行操作，以最无脑的方式实现所有步骤，它将不会很复杂，并且将是亚线性的。

M.H. Overmars和J. van Leeuwen。平面配置的维护。J. Comput. Syst. Sci.，23:166-204，1981。

- Joseph O'Rourke

---

除了你的答案之外，在许多情况下，理解论文的细节比实现它们更困难。 - Saeed Amiri

Answer 2

关于O'Rourke教授的问题，他对计算几何学的了解远远超过我，但我认为一个“机械”的OvL实现（即没有重新平衡的实现）在最坏情况下不可能是亚线性的。

幸运的是，自1981年以来，我们在数据结构方面取得了一些进展。特别是，由于分摊保证足够，伸展树（1985）适合存储凸包和合并树。Austern et al. (2003)提出了一种很好的方法，将所需的额外字段的维护与复杂的平衡操作分开，因此您可以只编写棘手的部分一次。

实现伸展树的主要困难是伸展操作，即使这个操作比插入红黑树还简单得多。一旦伸展操作完成，拆分和连接伸展树就变得容易了。要拆分，请将要拆分的节点伸展到其后并切断其右子节点。要连接，请将第一个树的最右侧节点伸展，并将第二个树作为该节点的右子节点。

- hello this is dog

---

那么，您的意思是整个算法中唯一棘手的部分就是实现伸展树？ - eold

是的，我承认错误：重新平衡是必要的，否则一个糟糕的序列将会把树变成一条路径。可以一直推迟重新平衡直到需要，但也可以使用你所说的伸展树。 - Joseph O'Rourke

Answer 3

我假设总共有N个数据点，而复杂外壳由M个点定义。

维护凸包应该比首次构建凸包要容易得多（也更便宜）。

删除现有数据点

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)

- martino

---

请注意，删除操作可能会导致从凸壳中删除O(N)个点。插入操作也是如此，可能会导致O(N)个新点成为凸壳的一部分。 - eold