Dynamic Geometric Set Cover and Hitting Set

DOI10.1145/3551639arXiv2003.00202WikidataQ114070910 ScholiaQ114070910MaRDI QIDQ6058268

No author found.

Publication date: 31 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Abstract: 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 $mathbb{R}^1$ and $mathbb{R}^2$. The first framework uses bootstrapping and gives a $(1+varepsilon)$-approximate data structure for dynamic interval set cover in $mathbb{R}^1$ with $O(n^{a}lpha/varepsilon)$ amortized update time for any constant $alpha>0$; in $mathbb{R}^2$, this method gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set with $O(n^{1/2+alpha})$ amortized update time. The second framework uses local modification, and leads to a $(1+varepsilon)$-approximate data structure for dynamic interval hitting set in $mathbb{R}^1$ with $widetildeO(1/varepsilon)$ amortized update time; in $mathbb{R}^2$, it gives $O(1)$-approximate data structures for unit-square (and quadrant) set cover and hitting set in the extit{partially} dynamic settings with $widetildeO(1)$ amortized update time.

Full work available at URL: https://arxiv.org/abs/2003.00202

zbMATH Keywords

dynamic data structuresgeometric hitting setgeometric set cover

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (3)

Geometric Set Cover and Hitting Sets for Polytopes in R ⋮ Dynamic Euclidean bottleneck matching ⋮ A PTAS for the horizontal rectangle stabbing problem

This page was built for publication: Dynamic Geometric Set Cover and Hitting Set