eol*_*old 8 algorithm complexity-theory dynamic convex-hull computational-geometry
我需要解决动态凸包算法问题,即保持2D点的凸包,我可以添加和删除点.
天真的做法很明显O(N); 无论何时N添加/删除其中一个点,我们都会从头开始重新计算凸包.但是,我无法承受线性时间,因此我正在寻找一种次线性算法.到目前为止,我已经找到了一堆纸,所有这些都描述了一些具有疯狂时间限制的复杂算法,这需要花费很长时间才能实现.即使是最古老的高效算法,由于Overmars和Leeuween,这O(log^2 N)似乎太复杂了.(像往常一样,这些论文中描述的大多数算法在结构/算法方面都有很多依赖性来自其他参考文献)
我正在寻找更简单,更不一定新颖的东西,在最坏的情况下(例如O(sqrt N))在线性方面表现优于线性.最后,我不介意时间是否摊销.有任何想法吗？
(简单来说,我主要是指不需要超过几百行代码的东西.)
我认为你所追求的并不存在.Overmars和vanLeeuwen算法并不复杂,在某种意义上似乎是必要的.首先,将问题改为分别维护上船体和下船体.其次,通过分而治之来构建每个,但保留中间树结构,以便你知道1/2套,1/4套等的船体.现在,当你删除一个点时,你只重新计算树中的祖先.添加一个点时,您会发现它加入了哪个叶子,然后再次向上重新计算到根目录.
我想如果你忽略了他们论文中的细节,只是按照这个高级草图,并以最无意识的方式实现所有步骤,它将不会复杂,并且将是次线性的.
MH Overmars和J. van Leeuwen.维护飞机中的配置. J. Comput.SYST.科学.,23:166-204,1981.