{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:36Z","timestamp":1787337576225,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814026"],"award-info":[{"award-number":["CCF-1814026"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814172"],"award-info":[{"award-number":["CCF-1814172"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirements) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in one and two dimensions, which significantly improve and extend the previous results. Our results include the following: (1) The first data structure for [Formula: see text]-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of [Formula: see text], improving the [Formula: see text] bound of Agarwal et\u00a0al. [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs.\u00a0Leibniz Int.\u00a0Proc.\u00a0Inform.\u00a0164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27; ACM Trans.\u00a0Algorithms, 18 (2022), 40], where [Formula: see text] denotes an arbitrarily small constant. (2) A data structure for [Formula: see text]-approximate dynamic unit-square set cover with [Formula: see text] amortized update time, substantially improving the [Formula: see text] update time of Agarwal et\u00a0al. (3)\u00a0A data structure for [Formula: see text]-approximate dynamic square set cover with [Formula: see text] randomized amortized update time, improving the [Formula: see text] update time of Chan and He [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs.\u00a0Leibniz Int.\u00a0Proc.\u00a0Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020; J. Comput. Geom., 13 (2022), pp. 90\u2013114]. (4) A data structure for [Formula: see text]-approximate dynamic two-dimensional half-plane set cover with [Formula: see text] randomized amortized update time. The previous solution for a half-plane set cover by Chan and He [ Proceedings of the 37 th International Symposium on Computational Geometry, LIPIcs.\u00a0Leibniz Int.\u00a0Proc.\u00a0Inform.\u00a0189, Schloss Dagstuhl - Leibniz Center for Informatics, 2021, 25; J. Comput. Geom., 13 (2022), pp. 90\u2013114] is slower and can only report the size of the approximate solution. (5) The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for [Formula: see text]-approximate dynamic weighted interval set cover with [Formula: see text] amortized update time and a data structure for [Formula: see text]-approximate dynamic weighted unit-square set cover with [Formula: see text] amortized update time.<\/jats:p>","DOI":"10.1137\/23m1596582","type":"journal-article","created":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T03:44:00Z","timestamp":1749095040000},"page":"664-701","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Geometric Set Cover, Revisited"],"prefix":"10.1137","volume":"54","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2518-1114","authenticated-orcid":true,"given":"Qizheng","family":"He","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California Santa Barbara, Santa Barbara, CA 93106 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7015-1988","authenticated-orcid":true,"given":"Jie","family":"Xue","sequence":"additional","affiliation":[{"name":"Computer Science, New York University Shanghai, Shanghai, 200126 China."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,6,5]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"A. Abboud, R. Addanki, F. Grandoni, D. Panigrahi, and B. Saha, Dynamic set cover: Improved algorithms and lower bounds, in Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 2019, pp. 114\u2013125, https:\/\/doi.org\/10.1145\/3313276.","DOI":"10.1145\/3313276.3316376"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/3551639"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/223\/03131"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9517-2"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00099-6"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya, M. Henzinger, D. Nanongkai, and X. Wu, Dynamic set cover: Improved amortized and worst-case update time, in Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 2537\u20132549, https:\/\/doi.org\/10.1137\/1.9781611976465.","DOI":"10.1137\/1.9781611976465.150"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.12.018"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9410-z"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.04.001"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"T. M. Chan, E. Grant, J. K\u00f6nemann, and M. Sharpe, Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling, in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 1576\u20131585.","DOI":"10.1137\/1.9781611973099.125"},{"key":"ref13","unstructured":"T. M. Chan and Q. He, Faster approximation algorithms for geometric set cover, in Proceedings of the 36th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2020.27."},{"key":"ref14","first-page":"90","volume":"13","author":"Chan T. M.","year":"2022","journal-title":"J. Comput. Geom."},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.12.005"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, Algorithms for polytope covering and approximation, in Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS), 1993, pp. 246\u2013252.","DOI":"10.1007\/3-540-57155-8_252"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1273-8"},{"key":"ref19","unstructured":"S. Compton, S. Mitrovic, and R. Rubinfeld, New partitioning techniques and faster algorithms for approximate interval scheduling, in Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs Leibniz Int. Proc. Inform. 261, Schloss Dagstuhl - Leibniz Center for Informatics, 2023, 45, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2023.45."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"T. Erlebach and E. J. van Leeuwen, PTAS for weighted set cover on unit squares, in Proceedings of the 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX), 2010, pp. 166\u2013177, https:\/\/doi.org\/10.1007\/978-3-642-15369-3_13.","DOI":"10.1007\/978-3-642-15369-3_13"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krishnaswamy, A. Kumar, and D. Panigrahi, Online and dynamic algorithms for set cover, in Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), 2017, pp. 537\u2013550, https:\/\/doi.org\/10.1145\/3055399.","DOI":"10.1145\/3055399.3055493"},{"key":"ref23","first-page":"65","volume":"3","author":"Har-Peled S.","year":"2012","journal-title":"J. Comput. Geom."},{"key":"ref24","unstructured":"M. Henzinger, S. Neumann, and A. Wiese, Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles, in Proceedings of the 36th Symposium on Computational Geometry (SoCG), 2020, pp. 51:1\u201351:14, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2020.51."},{"key":"ref25","unstructured":"A. Khan, A. Lonkar, S. Rahul, A. Subramanian, and A. Wiese, Online and dynamic algorithms for geometric set cover and hitting set, in Proceedings of the 39th Symposium on Computational Geometry (SoCG), LIPIcs Leibniz Int. Proc. Inform. 258, Schloss Dagstuhl - Leibniz Center for Informatics, 2023, 46, https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2023.46."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek, R. Seidel, and E. Welzl, How to net a lot with little: Small \\(\\varepsilon\\)-nets for disks and halfspaces, in Proceedings of the 6th Symposium on Computational Geometry (SoCG), ACM, 1990, pp. 16\u201322, https:\/\/doi.org\/10.1145\/98524.98530.","DOI":"10.1145\/98524.98530"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/14099317X"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9285-9"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"K. Varadarajan, Weighted geometric set cover via quasi-uniform sampling, in Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010, pp. 641\u2013648.","DOI":"10.1145\/1806689.1806777"},{"key":"ref31","unstructured":"V. V. Williams, On some fine-grained questions in algorithms and complexity, in Proceedings of the ICM, Vol. 3, World Scientific, 2018, pp. 3431\u20133472, https:\/\/people.csail.mit.edu\/virgi\/eccentri.pdf."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1596582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:32Z","timestamp":1787336312000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1596582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,5]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/23M1596582"],"URL":"https:\/\/doi.org\/10.1137\/23m1596582","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,5]]}}}