Incremental and decremental maintenance of planar width
Incremental and decremental maintenance of planar width
复制标题
平面宽度的增量和减量维护
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
D. Eppstein
我们提出了一种算法，用于保持平面点集的宽度动态，点插入或删除。我们的算法每次更新的时间为O（kn^n），其中k是更新在凸船体中引起的变化量，n是集合中的点的数量，并且n是任意小的常数。对于增量或减量更新序列，每次更新的摊销时间是O（n^n）。
We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^epsilon) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and epsilon is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^epsilon).