{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T16:59:05Z","timestamp":1774803545634,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T00:00:00Z","timestamp":1557360000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T00:00:00Z","timestamp":1557360000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-11-61359"],"award-info":[{"award-number":["CCF-11-61359"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-14-08846"],"award-info":[{"award-number":["IIS-14-08846"]}],"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-15-13816"],"award-info":[{"award-number":["CCF-15-13816"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ISS-14-47554"],"award-info":[{"award-number":["ISS-14-47554"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-15-1-0408"],"award-info":[{"award-number":["W911NF-15-1-0408"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2012\/229"],"award-info":[{"award-number":["2012\/229"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s00454-019-00099-6","type":"journal-article","created":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T00:10:03Z","timestamp":1557447003000},"page":"460-482","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Near-Linear Algorithms for Geometric Hitting Sets and Set Covers"],"prefix":"10.1007","volume":"63","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0397-8971","authenticated-orcid":false,"given":"Jiangwei","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,9]]},"reference":[{"key":"99_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909), pp. 180\u2013186. SIAM, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.21"},{"key":"99_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol. 223, pp. 1\u201356. American Mathematical Society, Providence (1999)","DOI":"10.1090\/conm\/223\/03131"},{"issue":"1\u20132","key":"99_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-011-9517-2","volume":"63","author":"PK Agarwal","year":"2012","unstructured":"Agarwal, P.K., Ezra, E., Sharir, M.: Near-linear approximation algorithms for geometric hitting sets. Algorithmica 63(1\u20132), 1\u201325 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"99_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00454-010-9323-7","volume":"47","author":"N Alon","year":"2012","unstructured":"Alon, N.: A non-linear lower bound for planar epsilon-nets. Discrete Comput. Geom. 47(2), 235\u2013244 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"99_CR5","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"99_CR6","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size $\\varepsilon $-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"99_CR7","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B Aronov","year":"2008","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"99_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(6), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"issue":"4","key":"99_CR9","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems. I. Static-to-dynamic transformation. J. Algorithms 1(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"issue":"1","key":"99_CR10","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(1), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"C","key":"99_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.comgeo.2015.12.002","volume":"53","author":"N Bus","year":"2016","unstructured":"Bus, N., Garg, S., Mustafa, N.H., Ray, S.: Tighter estimates for e-nets for disks. Comput. Geom. Theory Appl. 53(C), 27\u201335 (2016)","journal-title":"Comput. Geom. Theory Appl."},{"key":"99_CR12","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909), pp. 892\u2013901. SIAM, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.97"},{"key":"99_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Proceedings of the 25th Annual Symposium on Computational Geometry (SoCG\u201909), pp. 333\u2013340. ACM, New York (2009)","DOI":"10.1145\/1542362.1542420"},{"key":"99_CR14","unstructured":"Chan, T.M., Tsakalidis, K.: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. In: Proceedings of the 31th Annual Symposium on Computational Geometry (SoCG\u201915). LIPIcs. Leibniz International Proceedings in Informatics, vol. 34, pp. 719\u2013732. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2015)"},{"issue":"3","key":"99_CR15","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: a new approach to query answering. SIAM J. Comput. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"99_CR16","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Welzl, E.: Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom. 4(5), 467\u2013489 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"99_CR17","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/2390176.2390185","volume":"9","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms 9(1), 9:1\u20139:17 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"99_CR18","first-page":"246","volume-title":"Lecture Notes in Computer Science","author":"Kenneth L. Clarkson","year":"1993","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS\u201993), pp. 246\u2013252. Springer, Berlin (1993)"},{"issue":"2","key":"99_CR19","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"KL Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2), 488\u2013499 (1995)","journal-title":"J. ACM"},{"issue":"1","key":"99_CR20","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"99_CR21","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. McGraw-Hill, Boston (2009)","edition":"3"},{"key":"99_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"99_CR23","doi-asserted-by":"crossref","unstructured":"Ezra, E.E.: Small-size relative ($p,\\varepsilon $)-approximations for well-behaved range spaces. In: Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG\u201913), pp. 233\u2013242. ACM, New York (2013)","DOI":"10.1145\/2462356.2462363"},{"issue":"4","key":"99_CR24","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $\\ln n$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"99_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"99_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1006\/game.1999.0738","volume":"29","author":"Y Freund","year":"1999","unstructured":"Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games Econ. Behav. 29(1\u20132), 79\u2013103 (1999)","journal-title":"Games Econ. Behav."},{"key":"99_CR27","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"issue":"2","key":"99_CR28","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0167-6377(95)00032-0","volume":"18","author":"MD Grigoriadis","year":"1995","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: A sublinear-time randomized approximation algorithm for matrix games. Oper. Res. Lett. 18(2), 53\u201358 (1995)","journal-title":"Oper. Res. Lett."},{"key":"99_CR29","volume-title":"Geometric Approximation Algorithms. Mathematical Surveys and Monographs","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)"},{"issue":"2","key":"99_CR30","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $\\varepsilon $-nets and simplex range queries. Discrete Comput. Geom. 2(2), 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"99_CR31","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1007\/s00453-013-9771-6","volume":"70","author":"C Koufogiannakis","year":"2014","unstructured":"Koufogiannakis, C., Young, N.E.: A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica 70(4), 648\u2013674 (2014)","journal-title":"Algorithmica"},{"key":"99_CR32","unstructured":"Kupavskii, A., Mustafa, N., Pach, J.: New lower bounds for epsilon-nets. In: Proceedings of the 32nd International Symposium on Computational Geometry. LIPIcs. Leibniz International Proceedings in Informatics, vol. 51, pp. 54:1\u201354:16. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2016)"},{"key":"99_CR33","unstructured":"Lauen, S.: Geometric set cover and hitting sets for polytopes in $R^3$. In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science. LIPIcs. Leibniz International Proceedings in Informatics, vol. 1, pp. 479\u2013490. Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2008)"},{"key":"99_CR34","first-page":"26","volume-title":"Lecture Notes in Computer Science","author":"Philip M. Long","year":"2001","unstructured":"Long, P.M.: Using the pseudo-dimension to analyze approximation algorithms for integer programming. In: Proceedings of the 7th Workshop Algorithms Data Structures. Lecture Notes in Computer Science, vol. 2125, pp. 26\u201337. Springer, Berlin (2001)"},{"issue":"3","key":"99_CR35","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete Comput. Geom. 8(3), 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"99_CR36","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom."},{"key":"99_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"99_CR38","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pp. 541\u2013550. IEEE, Los Alamitos (2014)","DOI":"10.1109\/FOCS.2014.64"},{"issue":"4","key":"99_CR39","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"99_CR40","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1090\/S0894-0347-2012-00759-0","volume":"26","author":"J Pach","year":"2013","unstructured":"Pach, J., Tardos, G.: Tight lower bounds for the size of epsilon-nets. J. Am. Math. Soc. 26(3), 645\u2013658 (2013)","journal-title":"J. Am. Math. Soc."},{"issue":"2","key":"99_CR41","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"key":"99_CR42","doi-asserted-by":"crossref","unstructured":"Pyrga, E., Ray, S.: New existence proofs for $\\varepsilon $-nets. In: Proceedings of the 24th Annual Symposium on Computational Geometry (SoCG\u201908), pp. 199\u2013207. ACM, New York (2008)","DOI":"10.1145\/1377676.1377708"},{"key":"99_CR43","unstructured":"Shaul, H.: Range Searching: Emptiness, Reporting, and Approximate Counting. PhD thesis, Tel Aviv University (2011)"},{"key":"99_CR44","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.: Epsilon nets and union complexity. In: Proceedings of the 25th Annual Symposium on Computational Geometry (SoCG\u201909), pp. 11\u201316. ACM, New York (2009)","DOI":"10.1145\/1542362.1542366"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00099-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00099-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00099-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:45:59Z","timestamp":1589697959000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00099-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,9]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["99"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00099-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,9]]},"assertion":[{"value":"20 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}