DYNAMIC GEOMETRIC SET COVER, REVISITED

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirements) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in one and two dimensions, which significantly improve and extend the previous results. Our results include the following: (1) The first data structure for (1 + \varepsilon)approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O((log³ n)/\varepsilon), improving the O(n^\delta/\varepsilon) bound of Agarwal et al. [Proceedings of the 36th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27; ACM Trans. Algorithms, 18 (2022), 40], where δ > 0 denotes an arbitrarily_ small constant. (2) A data structure for O(1)-approximate dynamic unit-square set cover with 2^O(\surdlo\mathrm{g} n⁾ amortized update time, substantially improving the O(n¹/2+^\delta) update time of Agarwal et al. (3) A data structure for O(1)-approximate dynamic square set cover with O(n¹/2+^\delta) randomized amortized update time, improving the O(n²/3+^\delta) update time of Chan and He [Proceedings of the 36th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020; J. Comput. Geom., 13 (2022), pp. 90-114]. (4) A data structure for O(1)-approximate dynamic two-dimensional half-plane set cover with O(n¹⁷/23+^\delta) randomized amortized update time. The previous solution for a half-plane set cover by Chan and He [Proceedings of the 37th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 189, Schloss Dagstuhl - Leibniz Center for Informatics, 2021, 25; J. Comput. Geom., 13 (2022), pp. 90-114] is slower and can only report the size of the approximate solution. (5) The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o(1))-approximate dynamic weighted interval set cover with 2^O(\surdlo\mathrm{g} n lo\mathrm{g} lo\mathrm{g} n⁾ amortized update time and a data structure for O(1)-approximate dynamic weighted unit-square set cover with O(n^\delta) amortized update time.