More dynamic data structures for geometric set cover with sublinear update time
| Autor: | Chan, Timothy M., He, Qizheng |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.20382/jocg.v13i2a6 |
| Popis: | 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]. Journal of Computational Geometry, Vol. 13 No. 2: Special Issue of Selected Papers from SoCG 2021 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|