论文标题
动态几何套装和击打集
Dynamic geometric set cover and hitting set
论文作者
论文摘要
我们研究了可以插入或删除点和范围的几何集盖和击中集合的动态版本，我们希望有效地为当前问题实例维护（大致）最佳解决方案。虽然过去对它们的静态版本进行了广泛的研究，但令人惊讶的是，关于动态几何套装和击打集的知之甚少。例如，即使对于一维间隔设置盖和击中集的最基本情况，也不知道非平凡的结果。我们论文的主要贡献是两个框架，这些框架导致有效的数据结构，用于动态维护设定盖和击中集合，以$ \ MATHBB {R}^1 $和$ \ MATHBB {R}^2 $。第一个框架使用引导程序，并提供$（1+ \ varepsilon）$ - 在$ \ mathbb {r}^1 $中的动态间隔集盖的近似数据结构，并带有$ O（n^α/\ varepsilon）$（n^α/\ varepsilon）$ amortized更新时间的任何常数$α> 0 $;在$ \ mathbb {r}^2 $中，此方法给出了$ o（1）$ - 单位平方（和象限）设置封面的近似数据结构，并使用$ o（n^{1/2+α}）$ a amortized更新时间。第二个框架使用局部修改，并导致$（1+ \ varepsilon）$ - 用于$ \ mathbb {r}^1 $中的动态间隔命中的近似数据结构，并带有$ \ widetilde {o}（o}（1/\ varepsilon）$ amortized更新时间;在$ \ mathbb {r}^2 $中，它给出了$ o（1）$ - 单位方（和象限）设置封面的近似数据结构，并在\ textit {部分}中设置了使用$ \ widetilde {o}（o}（O}（1）$ amortized更新时间）中的Dynamic设置。
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in $\mathbb{R}^1$ and $\mathbb{R}^2$. The first framework uses bootstrapping and gives a $(1+\varepsilon)$-approximate data structure for dynamic interval set cover in $\mathbb{R}^1$ with $O(n^α/\varepsilon)$ amortized update time for any constant $α> 0$; in $\mathbb{R}^2$, this method gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+α})$ amortized update time. The second framework uses local modification, and leads to a $(1+\varepsilon)$-approximate data structure for dynamic interval hitting set in $\mathbb{R}^1$ with $\widetilde{O}(1/\varepsilon)$ amortized update time; in $\mathbb{R}^2$, it gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set in the \textit{partially} dynamic settings with $\widetilde{O}(1)$ amortized update time.
