2021/03/14 by Chan, Timothy M., He, Qizheng · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2103.07857
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(n2/3+δ) for an arbitrarily small constant δ>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(nlog n)-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier O(nlog n(loglog n)O(1)) result [SoCG 2020].