We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a constant-factor approximate maximum independent set for broad classes of fat objects in $d$ dimensions, where $d$ is assumed to be a constant, in sublinear \textit{worst-case} update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. For axis-aligned squares and hypercubes, our result improves upon all (recently announced) previous works. We obtain, in particular, a dynamic $(4+\epsilon)$-approximation for squares, with $O(\log^4 n)$ worst-case update time. Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with \textit{amortized} update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.
翻译:我们考虑的是保持大约最独立的一组插入和删除的几何对象的问题。 我们展示了数据结构, 这些数据结构维持了一个不变因素, 大致为最独立的设定, 用于大类脂肪物体, 以美元为维维度, 假设美元为常数, 以亚线性\ textit{ worst- case} 更新时间为基数。 这为动态独立设置提供了初步结果, 包括磁盘、 脂肪多边形及其高维等值。 对于轴对齐方形和超立方体, 我们的结果将改善所有( 最近宣布的) 以前的作品。 我们特别获得一个动态要素 $( 4 ⁇ epsilon) $- 以美元为基数, 以美元为底线性基数的基数 。 我们开发一个动态数据结构, 储存所有对象, 并提供最坏的基数, 以直径直方平方平方平方正值运行的时间段。 我们通过标准的方法, 可以使用这种结构获得最坏的时间算法更新 。