Dynamic geometric set cover and hitting set

Published

Journal Article

© Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020). We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in R1 and R2. The first framework uses bootstrapping and gives a (1 + ε)-approximate data structure for dynamic interval set cover in R1 with O(nα/ε) amortized update time for any constant α > 0; in R2, this method gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set with O(n1/2+α) amortized update time. The second framework uses local modification, and leads to a (1 + ε)-approximate data structure for dynamic interval hitting set in R1 with Oe(1/ε) amortized update time; in R2, it gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set in the partially dynamic settings with Oe(1) amortized update time.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Chang, HC; Suri, S; Xiao, A; Xue, J

Published Date

  • June 1, 2020

Published In

Volume / Issue

  • 164 /

International Standard Serial Number (ISSN)

  • 1868-8969

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.SoCG.2020.2

Citation Source

  • Scopus