License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13824/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; He, Qizheng

More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

pdf-format:
LIPIcs-SoCG-2021-25.pdf (0.7 MB)

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
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI