Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.25
URN: urn:nbn:de:0030-drops-138244
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13824/
Chan, Timothy M. ; He, Qizheng
More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time
| pdf-format: |
|
Abstract
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+δ}) 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(log log n)^{O(1)}) result [SoCG 2020].
BibTeX - Entry
@InProceedings{chan_et_al:LIPIcs.SoCG.2021.25,
author = {Chan, Timothy M. and He, Qizheng},
title = {{More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {25:1--25:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-184-9},
ISSN = {1868-8969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13824},
URN = {urn:nbn:de:0030-drops-138244},
doi = {10.4230/LIPIcs.SoCG.2021.25},
annote = {Keywords: Geometric set cover, approximation algorithms, dynamic data structures, sublinear algorithms, random sampling}
}
| Keywords: | Geometric set cover, approximation algorithms, dynamic data structures, sublinear algorithms, random sampling | |
| Seminar: | 37th International Symposium on Computational Geometry (SoCG 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 02.06.2021 |
