{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:12:37Z","timestamp":1742933557336,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_21","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T04:31:28Z","timestamp":1368765088000},"page":"221-232","source":"Crossref","is-referenced-by-count":3,"title":["Hitting and Piercing Rectangles Induced by a Point Set"],"prefix":"10.1007","author":[{"given":"Ninad","family":"Rajgopal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pradeesha","family":"Ashok","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sathish","family":"Govindarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhijit","family":"Khopkar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"21_CR1","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/j.comgeo.2008.02.005","volume":"42","author":"B. Aronov","year":"2009","unstructured":"Aronov, B., Aurenhammer, F., Hurtado, F., Langerman, S., Rappaport, D., Seara, C., Smorodinsky, S.: Small weak epsilon-nets. Computational Geometry\u00a042(5), 455\u2013462 (2009)","journal-title":"Computational Geometry"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Aronov, B., Chazelle, B., Edelsbrunner, H.: Points and triangles in the plane and halving planes in space, vol.\u00a06, pp. 435\u2013442 (1991)","DOI":"10.1007\/BF02574700"},{"issue":"6-7","key":"21_CR3","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.comgeo.2011.01.001","volume":"44","author":"B. Aronov","year":"2011","unstructured":"Aronov, B., Dulieu, M., Hurtado, F.: Witness (delaunay) graphs. Comput. Geom.\u00a044(6-7), 329\u2013344 (2011)","journal-title":"Comput. Geom."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Aronov, B., Dulieu, M., Hurtado, F.: Witness gabriel graphs. Computational Geometry (2011)","DOI":"10.1007\/978-3-642-22300-6_7"},{"issue":"7","key":"21_CR5","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 \u03b5-nets for axis-parallel rectangles and boxes. SIAM J. Comput.\u00a039(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"21_CR6","unstructured":"Ashok, P., Govindarajan, S., Kulkarni, J.: Small strong epsilon nets. In: CCCG, pp. 155\u2013158 (2010)"},{"issue":"2-3","key":"21_CR7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(82)90115-7","volume":"40","author":"I. B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I.: A generalization of carath\u00e9odory\u2019s theorem. Discrete Mathematics\u00a040(2-3), 141\u2013152 (1982)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"21_CR8","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s00454-010-9263-2","volume":"44","author":"A. Basit","year":"2010","unstructured":"Basit, A., Mustafa, N.H., Ray, S., Raza, S.: Hitting simplices with points in \u211d3. Discrete & Computational Geometry\u00a044(3), 637\u2013644 (2010)","journal-title":"Discrete & Computational Geometry"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF00181519","volume":"17","author":"E. Boros","year":"1984","unstructured":"Boros, E., F\u00fcredi, Z.: The number of triangles covering the center of an n-set. Geometriae Dedicata\u00a017, 69\u201377 (1984)","journal-title":"Geometriae Dedicata"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set. In: Proceedings of the 2012 Symposuim on Computational Geometry, pp. 293\u2013302. ACM (2012)","DOI":"10.1145\/2261250.2261293"},{"issue":"6","key":"21_CR11","doi-asserted-by":"publisher","first-page":"1138","DOI":"10.1137\/S0097539790179919","volume":"23","author":"B. Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Hershberger, J., Seidel, R., Sharir, M.: Selecting heavily covered points. SIAM J. Comput.\u00a023(6), 1138\u20131151 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"21_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/rsa.20246","volume":"34","author":"X. Chen","year":"2009","unstructured":"Chen, X., Pach, J., Szegedy, M., Tardos, G.: Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Struct. Algorithms\u00a034(1), 11\u201323 (2009)","journal-title":"Random Struct. Algorithms"},{"key":"21_CR13","unstructured":"Czyzowicz, J., Kranakis, E., Urrutia, J.: Dissections, cuts and triangulations. In: CCCG (1999)"},{"issue":"1","key":"21_CR14","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci.\u00a0410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"21_CR15","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M., Tanimoto, S.L.: Optimal packing and covering in the plane are np-complete. Inf. Process. Lett.\u00a012(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"21_CR16","unstructured":"Grant, E., Chan, T.M.: Exact algorithms and apx-hardness results for geometric set cover. In: CCCG (2011)"},{"issue":"1","key":"21_CR17","doi-asserted-by":"publisher","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\u00a032(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"issue":"3-4","key":"21_CR18","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF01903339","volume":"51","author":"M. Katchalski","year":"1988","unstructured":"Katchalski, M., Meir, A.: On empty triangles determined by points in the plane. Acta Mathematica Hungarica\u00a051(3-4), 323\u2013328 (1988)","journal-title":"Acta Mathematica Hungarica"},{"key":"21_CR19","first-page":"28","volume-title":"Proceedings of the 19th Annual Symposium on Foundations of Computer Science, SFCS 1978","author":"S. Lueker","year":"1978","unstructured":"Lueker, S.: A data structure for orthogonal range queries. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science, SFCS 1978, pp. 28\u201334. IEEE Computer Society, Washington, DC (1978)"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Springer (2002)","DOI":"10.1007\/978-1-4613-0039-7"},{"issue":"5","key":"21_CR21","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Operations Research Letters\u00a01(5), 194\u2013197 (1982)","journal-title":"Operations Research Letters"},{"issue":"4","key":"21_CR22","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"N.H. Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete & Computational Geometry\u00a044(4), 883\u2013895 (2010)","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"21_CR23","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1112\/jlms\/s1-21.4.291","volume":"1","author":"R. Rado","year":"1946","unstructured":"Rado, R.: A theorem on general measure. Journal of the London Mathematical Society\u00a01(4), 291\u2013300 (1946)","journal-title":"Journal of the London Mathematical Society"},{"issue":"3","key":"21_CR24","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1017\/S0963548303005984","volume":"13","author":"S. Smorodinsky","year":"2004","unstructured":"Smorodinsky, S., Sharir, M.: Selecting points that are heavily covered by pseudo-circles, spheres or rectangles. Combinatorics, Probability & Computing\u00a013(3), 389\u2013411 (2004)","journal-title":"Combinatorics, Probability & Computing"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T02:24:26Z","timestamp":1674527066000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}