Document Open Access Logo

Dynamic Geometric Set Cover and Hitting Set

Authors Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, Jie Xue

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.2.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
  • Department of Computer Science, Duke University, Durham, NC, USA
Hsien-Chih Chang
  • Department of Computer Science, Duke University, Durham, NC, USA
Subhash Suri
  • Department of Computer Science, University of California at Santa Barbara, CA, USA
Allen Xiao
  • Department of Computer Science, Duke University, Durham, NC, USA
Jie Xue
  • Department of Computer Science, University of California at Santa Barbara, CA, USA

Funding

  • Agarwal, Pankaj K.: NSF grants CCF-15-13816, CCF-15-46392, and IIS-14-08846; ARO grant W911NF-15-1-0408; BSF Grant 2012/229 from the U.S.-Israel Binational Science Foundation.
  • Chang, Hsien-Chih: NSF grants CCF-15-13816, CCF-15-46392, and IIS-14-08846; ARO grant W911NF-15-1-0408; BSF Grant 2012/229 from the U.S.-Israel Binational Science Foundation.
  • Suri, Subhash: NSF grant CCF-18-14172.
  • Xiao, Allen: NSF grants CCF-15-13816, CCF-15-46392, and IIS-14-08846; ARO grant W911NF-15-1-0408; BSF Grant 2012/229 from the U.S.-Israel Binational Science Foundation.
  • Xue, Jie: NSF grant CCF-18-14172.

Cite AsGet BibTex

Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic Geometric Set Cover and Hitting Set. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.2

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 ℝ¹ and ℝ². The first framework uses bootstrapping and gives a (1+ε)-approximate data structure for dynamic interval set cover in ℝ¹ with O(n^α/ε) amortized update time for any constant α > 0; in ℝ², this method gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set with O(n^(1/2+α)) amortized update time. The second framework uses local modification, and leads to a (1+ε)-approximate data structure for dynamic interval hitting set in ℝ¹ with Õ(1/ε) amortized update time; in ℝ², it gives O(1)-approximate data structures for unit-square (and quadrant) set cover and hitting set in the partially dynamic settings with Õ(1) amortized update time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Geometric set cover
  • Geometric hitting set
  • Dynamic data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 114-125. ACM, 2019. Google Scholar
  2. Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic geometric set cover and hitting set. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.00202.
  3. Pankaj K. Agarwal and Jiangwei Pan. Near-linear algorithms for geometric hitting sets and set covers. In Proceedings of the thirtieth annual symposium on Computational geometry, page 271. ACM, 2014. Google Scholar
  4. Pankaj K. Agarwal, Junyi Xie, Jun Yang, and Hai Yu. Monitoring continuous band-join queries over dynamic data. In 16th International Symposium on Algorithms and Computation (ISAAC), pages 349-359. Springer, 2005. Google Scholar
  5. Piotr Berman and Bhaskar DasGupta. Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica, 17(4):331-356, 1997. Google Scholar
  6. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano. Design of dynamic algorithms via primal-dual method. In International Colloquium on Automata, Languages, and Programming, pages 206-218. Springer, 2015. Google Scholar
  7. Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233-235, 1979. Google Scholar
  8. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing, pages 624-633. ACM, 2014. Google Scholar
  9. Thomas Erlebach and Erik Jan Van Leeuwen. Ptas for weighted set cover on unit squares. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 166-177. Springer, 2010. Google Scholar
  10. Shashidhara K. Ganjugunte. Geometric hitting sets and their variants. PhD thesis, Duke University, 2011. Google Scholar
  11. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 537-550. ACM, 2017. Google Scholar
  12. Juris Hartmanis. Computers and intractability: a guide to the theory of np-completeness. Siam Review, 24(1):90, 1982. Google Scholar
  13. David S. Johnson. Approximation algorithms for combinatorial problems. Journal of computer and system sciences, 9(3):256-278, 1974. Google Scholar
  14. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. Journal of Computer and System Sciences, 74(3):335-349, 2008. Google Scholar
  15. László Lovász. On the ratio of optimal integral and fractional covers. Discrete mathematics, 13(4):383-390, 1975. Google Scholar
  16. Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182-196, 1984. Google Scholar
  17. Nimrod Megiddo and Arie Tamir. On the complexity of locating linear facilities in the plane. Operations research letters, 1(5):194-197, 1982. Google Scholar
  18. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact