More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
复制标题
DOI：
10.4230/lipics.socg.2021.25
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan;Qizheng He
中科院分区：
文献类型：
--
作者：
Timothy M. Chan;Qizheng He
我们研究几何集覆盖问题在动态设置，允许插入和删除的点和对象。我们提出了第一个动态的数据结构，可以保持一个O（1）$-近似的次线性更新时间为轴对齐的正方形在2D中的集合覆盖。更准确地说，我们得到随机更新时间$O（n^{2/3+\delta}）$对于一个任意小的常数$\delta>0$。此前，Agarwal、Chang、Suri、Xiao和Xue [SoCG 2020]仅对单位正方形已知具有次线性更新时间的动态几何集覆盖数据结构。如果只需要解的近似大小，那么我们也可以获得2D中的圆盘和3D中的半空间的次线性摊销更新时间。作为副产品，我们的动态集合覆盖技术也为2D磁盘和3D半空间的静态集合覆盖产生了最佳随机$O（n\log n）$时间算法，改进了我们早期的$O（n\log n（\log\log n）^{O（1）}）$结果[SoCG 2020]。
We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an $O(1)$-approximation in sublinear update time for set cover for axis-aligned squares in 2D. More precisely, we obtain randomized update time $O(n^{2/3+\delta})$ for an arbitrarily small constant $\delta>0$. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D. As a byproduct, our techniques for dynamic set cover also yield an optimal randomized $O(n\log n)$-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier $O(n\log n(\log\log n)^{O(1)})$ result [SoCG 2020].