{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:38:21Z","timestamp":1772908701042,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,7,30]],"date-time":"2008-07-30T00:00:00Z","timestamp":1217376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00224-008-9135-9","type":"journal-article","created":{"date-parts":[[2008,7,29]],"date-time":"2008-07-29T18:43:39Z","timestamp":1217357019000},"page":"446-469","source":"Crossref","is-referenced-by-count":33,"title":["Covering Many or Few Points with Unit Disks"],"prefix":"10.1007","volume":"45","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Cabello","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sariel","family":"Har-Peled","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,7,30]]},"reference":[{"key":"9135_CR1","series-title":"LNCS","volume-title":"ESA 2002","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Hagerup, T., Ray, R., Sharir, M., Smid, M., Welzl, E.: Translating a planar object to maximize point containment. In: ESA 2002. LNCS, vol.\u00a02461. Springer, Berlin (2002)"},{"issue":"2","key":"9135_CR2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33(2), 201\u2013226 (2002)","journal-title":"Algorithmica"},{"key":"9135_CR3","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)","edition":"2"},{"key":"9135_CR4","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":"9135_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0925-7721(02)00128-1","volume":"25","author":"P. Bose","year":"2003","unstructured":"Bose, P., van Kreveld, M., Maheshwari, A., Morin, P., Morrison, J.: Translating a regular grid over a point set. Comput. Geom. Theory Appl. 25, 21\u201334 (2003)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9135_CR6","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.comgeo.2007.10.001","volume":"40","author":"S. Cabello","year":"2008","unstructured":"Cabello, S., D\u00edaz B\u00e1\u00f1ez, J.M., Seara, C., Sellar\u00e8s, J.A., Urrutia, J., Ventura, I.: Covering point sets with two disjoint disks or squares. Comput. Geom. Theory Appl. 40, 195\u2013206 (2008)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9135_CR7","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B. Chazelle","year":"2001","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York (2001)"},{"key":"9135_CR8","first-page":"983","volume-title":"Handbook of Discrete and Computational Geometry","author":"B. Chazelle","year":"2004","unstructured":"Chazelle, B.: The discrepancy method in computational geometry. In: Handbook of Discrete and Computational Geometry, pp.\u00a0983\u2013996. CRC, Boca Raton (2004)"},{"key":"9135_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02238188","volume":"36","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Lee, D.T.: On a circle placement problem. Computing 36, 1\u201316 (1986)","journal-title":"Computing"},{"key":"9135_CR10","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":"9135_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 2nd edn. Springer, Berlin (2000)","edition":"2"},{"key":"9135_CR12","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1287\/mnsc.27.7.848","volume":"27","author":"Z. Drezner","year":"1981","unstructured":"Drezner, Z.: On a modified one-center model. Manag. Sci. 27, 848\u2013851 (1981)","journal-title":"Manag. Sci."},{"key":"9135_CR13","first-page":"83","volume":"2","author":"Z. Drezner","year":"1994","unstructured":"Drezner, Z., Wesolowsky, G.O.: Finding the circle or rectangle containing the minimum weight of points. Location Sci. 2, 83\u201390 (1994)","journal-title":"Location Sci."},{"key":"9135_CR14","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A. Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of O(n 2) problems in computational geometry. Comput. Geom. Theory Appl. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9135_CR15","first-page":"529","volume-title":"Handbook of Discrete and Computational Geometry","author":"D. Halperin","year":"2004","unstructured":"Halperin, D.: Arrangements. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp.\u00a0529\u2013562. CRC, Boca Raton (2004)"},{"issue":"1","key":"9135_CR16","first-page":"130","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.\u00a0ACM 32(1), 130\u2013136 (1985)","journal-title":"J.\u00a0ACM"},{"key":"9135_CR17","doi-asserted-by":"crossref","first-page":"1859","DOI":"10.1016\/S0305-0548(01)00063-6","volume":"29","author":"M.J. Katz","year":"2002","unstructured":"Katz, M.J., Kedem, K., Segal, M.: Improved algorithms for placing undesirable facilities. Comput. Oper. Res. 29, 1859\u20131872 (2002)","journal-title":"Comput. Oper. Res."},{"key":"9135_CR18","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"M.J. Katz","year":"1997","unstructured":"Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26, 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"key":"9135_CR19","volume-title":"Algorithm Design","author":"J. Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley, Reading (2005)"},{"key":"9135_CR20","doi-asserted-by":"crossref","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, 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9135_CR21","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1006\/jcss.1995.1018","volume":"50","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: Approximations and optimal geometric divide-an-conquer. J.\u00a0Comput. Syst. Sci. 50, 203\u2013208 (1995)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9135_CR22","first-page":"39","volume-title":"Location Analysis: Theory and Applications","author":"F. Plastria","year":"2001","unstructured":"Plastria, F.: Continuous covering location problems. In: Hamacher, H., Drezner, Z. (eds.) Location Analysis: Theory and Applications, pp.\u00a039\u201383. Springer, Berlin (2001), Chap.\u00a02"},{"key":"9135_CR23","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/BF02574706","volume":"6","author":"M. Sharir","year":"1991","unstructured":"Sharir, M.: On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom. 6, 593\u2013613 (1991)","journal-title":"Discrete Comput. Geom."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9135-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9135-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9135-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:36Z","timestamp":1558698696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9135-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,30]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9135"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9135-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7,30]]}}}