TY - GEN
T1 - More dynamic data structures for geometric set cover with sublinear update time
AU - Chan, Timothy M.
AU - He, Qizheng
N1 - Funding Information:
Supported in part by NSF Grant CCF-1814026.
Publisher Copyright:
© Timothy M. Chan and Qizheng He; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).
PY - 2021/6/1
Y1 - 2021/6/1
N2 - 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(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].
AB - 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(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].
KW - Approximation algorithms
KW - Dynamic data structures
KW - Geometric set cover
KW - Random sampling
KW - Sublinear algorithms
UR - http://www.scopus.com/inward/record.url?scp=85108191975&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108191975&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2021.25
DO - 10.4230/LIPIcs.SoCG.2021.25
M3 - Conference contribution
AN - SCOPUS:85108191975
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Computational Geometry, SoCG 2021
A2 - Buchin, Kevin
A2 - de Verdiere, Eric Colin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th International Symposium on Computational Geometry, SoCG 2021
Y2 - 7 June 2021 through 11 June 2021
ER -