{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T08:04:28Z","timestamp":1749110668655},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,5,6]],"date-time":"2011-05-06T00:00:00Z","timestamp":1304640000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9517-2","type":"journal-article","created":{"date-parts":[[2011,5,5]],"date-time":"2011-05-05T18:00:58Z","timestamp":1304618458000},"page":"1-25","source":"Crossref","is-referenced-by-count":11,"title":["Near-Linear Approximation Algorithms for Geometric Hitting Sets"],"prefix":"10.1007","volume":"63","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[]},{"given":"Esther","family":"Ezra","sequence":"additional","affiliation":[]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,6]]},"reference":[{"key":"9517_CR1","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1145\/1810959.1811001","volume-title":"Proc. 26th Annu. Sympos. Comput. Geom.","author":"P. Afshani","year":"2010","unstructured":"Afshani, P., Arge, L., Larsen, K.D.: Orthogonal range reporting: query lower bounds, optimal structures in 3d, and higher dimensional improvements. In: Proc. 26th Annu. Sympos. Comput. Geom., pp. 240\u2013246 (2010)"},{"key":"9517_CR2","first-page":"809","volume-title":"Handbook of Discrete and Computational Geometry","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K.: Range searching. In: Goodman, J., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 809\u2013838. CRC Press, New York (2004)","edition":"2"},{"key":"9517_CR3","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matou\u0161ek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27, 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"key":"9517_CR4","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput. 29, 912\u2013953 (2000)","journal-title":"SIAM J. Comput."},{"key":"9517_CR5","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/978-3-642-02085-8_22","volume-title":"Proc. 5th IEEE Internat. Conf. Distrib. Comput. Sensor Sys.","author":"P.K. Agarwal","year":"2009","unstructured":"Agarwal, P.K., Ezra, E., Ganjugunte, S.: Efficient sensor placement for surveillance problems. In: Proc. 5th IEEE Internat. Conf. Distrib. Comput. Sensor Sys., pp. 301\u2013314 (2009)"},{"key":"9517_CR6","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1137\/S009753979426616X","volume":"27","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Schwarzkopf, O.: Computing many faces in arrangements of lines and segments. SIAM J. Comput. 27, 491\u2013505 (1998)","journal-title":"SIAM J. Comput."},{"key":"9517_CR7","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1090\/conm\/453\/08794","volume-title":"Surveys on Discrete and Computational Geometry","author":"P.K. Agarwal","year":"2008","unstructured":"Agarwal, P.K., Pach, J., Sharir, M.: State of the union (of geometric objects). In: Goodman, J., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry, pp. 9\u201348. Am. Math. Soc., Providence (2008)"},{"key":"9517_CR8","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/B978-044482537-7\/50003-6","volume-title":"Handbook of Computational Geometry","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Sharir, M.: Arrangements and their applications. In: Sack, J., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 49\u2013119. Elsevier, Amsterdam (2000)"},{"key":"9517_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1567274.1567275","volume":"34","author":"P.K. Agarwal","year":"2009","unstructured":"Agarwal, P.K., Xie, J., Yang, J., Yu, H.: Input-sensitive scalable continuous join query processing. ACM Trans. Database Syst. 34, 1\u201341 (2009)","journal-title":"ACM Trans. Database Syst."},{"key":"9517_CR10","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bound for the union of locally fat objects in the plane. Unpublished manuscript, 2011"},{"key":"9517_CR11","doi-asserted-by":"crossref","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B. Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size \u03b5-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39, 3248\u20133882 (2010)","journal-title":"SIAM J. Comput."},{"key":"9517_CR12","doi-asserted-by":"crossref","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, 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"key":"9517_CR13","doi-asserted-by":"crossref","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 dimensions. Discrete Comput. Geom. 14, 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9517_CR14","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"9517_CR15","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/3-540-57155-8_252","volume-title":"Proc. 3rd Workshop on Algorithms and Data Structures","author":"K.L. Clarkson","year":"1993","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: Proc. 3rd Workshop on Algorithms and Data Structures, pp. 246\u2013252 (1993)"},{"key":"9517_CR16","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9517_CR17","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"K.L. Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37, 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9517_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","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":"9517_CR19","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17, 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"9517_CR20","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/BF02187745","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel, R., Sharir, M., Snoeyink, J.: On arrangements of Jordan arcs with three intersections per pair. Discrete Comput. Geom. 4, 523\u2013539 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9517_CR21","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.ipl.2005.03.010","volume":"95","author":"G. Even","year":"2005","unstructured":"Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95, 358\u2013362 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9517_CR22","first-page":"778","volume-title":"Proc. 22nd Annu. ACM\u2013SIAM Sympos. Discrete. Algo.","author":"E. Ezra","year":"2011","unstructured":"Ezra, E., Aronov, B., Sharir, M.: Improved bound for the union of fat triangles. In: Proc. 22nd Annu. ACM\u2013SIAM Sympos. Discrete. Algo., pp. 778\u2013785 (2011)"},{"key":"9517_CR23","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln\u2009n for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9517_CR24","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R. Fowler","year":"1981","unstructured":"Fowler, R., Paterson, M., Tanimoto, S.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"9517_CR25","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G.N. Frederickson","year":"1984","unstructured":"Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: Sorted matrices. SIAM J. Comput. 13, 14\u201330 (1984)","journal-title":"SIAM J. Comput."},{"key":"9517_CR26","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9517_CR27","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: \u03b5-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9517_CR28","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"9517_CR29","first-page":"479","volume-title":"Proc. 25th Int. Sympos. Theoret. Aspects Comput. Sci.","author":"S. Laue","year":"2008","unstructured":"Laue, S.: Geometric set cover and hitting sets for polytopes in \u211d3. In: Proc. 25th Int. Sympos. Theoret. Aspects Comput. Sci., pp. 479\u2013490 (2008)"},{"key":"9517_CR30","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1137\/070684483","volume":"38","author":"H. Kaplan","year":"2008","unstructured":"Kaplan, H., Rubin, N., Sharir, M., Verbin, E.: Efficient colored orthogonal range counting. SIAM J. Comput. 38, 982\u20131011 (2008)","journal-title":"SIAM J. Comput."},{"key":"9517_CR31","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K. Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1, 59\u201371 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"9517_CR32","unstructured":"King, J., Kirkpatrick, D.: Improved approximation for guarding simple galleries from the perimeter. arXiv:1001.4231"},{"key":"9517_CR33","first-page":"357","volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"D.E. Knuth","year":"1976","unstructured":"Knuth, D.E., Yao, A.C-C.: The complexity of nonuniform random number generation. In: Traub, J.F. (ed.) Algorithms and Complexity: New Directions and Recent Results, pp. 357\u2013428. Academic Press, New York (1976)"},{"key":"9517_CR34","doi-asserted-by":"crossref","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., Theory Appl. 2, 169\u2013186 (1992)","journal-title":"Comput. Geom., Theory Appl."},{"key":"9517_CR35","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01840386","volume":"5","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4her, S.: Dynamic fractional cascading. Algorithmica 5, 215\u2013241 (1990)","journal-title":"Algorithmica"},{"key":"9517_CR36","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/1542362.1542367","volume-title":"Proc. 25th Annu. ACM Sympos. Comput. Geom.","author":"N.H. Mustafa","year":"2009","unstructured":"Mustafa, N.H., Ray, S.: PTAS for geometric hitting set problems via local search. In: Proc. 25th Annu. ACM Sympos. Comput. Geom., pp. 17\u201322 (2009)"},{"key":"9517_CR37","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0304-3975(98)00336-3","volume":"246","author":"F. Nielsen","year":"2000","unstructured":"Nielsen, F.: Fast stabbing of boxes in high dimensions. Theor. Comput. Sci. 246, 53\u201372 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9517_CR38","doi-asserted-by":"crossref","first-page":"1745","DOI":"10.1137\/S0097539700382169","volume":"31","author":"J. Pach","year":"2002","unstructured":"Pach, J., Tardos, G.: On the boundary complexity of the union of fat triangles. SIAM J. Comput. 31, 1745\u20131760 (2002)","journal-title":"SIAM J. Comput."},{"key":"9517_CR39","doi-asserted-by":"crossref","unstructured":"Pach, J., Tardos, G.: Tight lower bounds for the size of \u03b5-nets. In: Proc. 27th Annu. ACM Sympos. Comput. Geom. (2011, to appear)","DOI":"10.1145\/1998196.1998271"},{"key":"9517_CR40","first-page":"199","volume-title":"Proc. 24th Annu. Sympos. Comput. Geom.","author":"E. Pyrga","year":"2008","unstructured":"Pyrga, E., Ray, S.: New existence proofs for \u03b5-nets. In: Proc. 24th Annu. Sympos. Comput. Geom., pp. 199\u2013207 (2008)"},{"key":"9517_CR41","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"key":"9517_CR42","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1542362.1542366","volume-title":"Proc. 25th Annu. ACM Sympos. Comput. Geom.","author":"K. Varadarajan","year":"2009","unstructured":"Varadarajan, K.: Epsilon nets and union complexity. In: Proc. 25th Annu. ACM Sympos. Comput. Geom., pp. 11\u201316 (2009)"},{"key":"9517_CR43","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9517-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9517-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9517-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T14:50:58Z","timestamp":1560178258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9517-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,6]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9517"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9517-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,6]]}}}