{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,23]],"date-time":"2023-12-23T11:31:04Z","timestamp":1703331064389},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T00:00:00Z","timestamp":1488758400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00454-017-9872-0","type":"journal-article","created":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T19:17:46Z","timestamp":1488827866000},"page":"985-1011","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Packing and Covering with Balls on Busemann Surfaces"],"prefix":"10.1007","volume":"57","author":[{"given":"Victor","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bertrand","family":"Estellon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guyslain","family":"Naves","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"issue":"2","key":"9872_CR1","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.comgeo.2005.12.001","volume":"34","author":"PK Agarwal","year":"2006","unstructured":"Agarwal, P.K., Mustafa, N.H.: Independent set of intersection graphs of convex objects in 2D. Comput. Geom. 34(2), 83\u201395 (2006)","journal-title":"Comput. Geom."},{"issue":"3","key":"9872_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/PL00009349","volume":"19","author":"N Alon","year":"1998","unstructured":"Alon, N.: Piercing $$d$$ d -intervals. Discrete Comput. Geom. 19(3), 333\u2013334 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"2\u20133","key":"9872_CR3","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0012-365X(02)00427-2","volume":"257","author":"N Alon","year":"2002","unstructured":"Alon, N.: Covering a hypergraph of subgraphs. Discrete Math. 257(2\u20133), 249\u2013254 (2002)","journal-title":"Discrete Math."},{"issue":"3","key":"9872_CR4","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02579383","volume":"6","author":"I B\u00e1r\u00e1ny","year":"1986","unstructured":"B\u00e1r\u00e1ny, I., Edmonds, J., Wolsey, L.A.: Packing and covering a tree by subtrees. Combinatorica 6(3), 221\u2013233 (1986)","journal-title":"Combinatorica"},{"key":"9872_CR5","volume-title":"Hypergraphs. North-Holland Mathematical Library","author":"C Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. North-Holland Mathematical Library, vol. 45. North-Holland, Amsterdam (1989)"},{"key":"9872_CR6","doi-asserted-by":"publisher","unstructured":"B\u00f6r\u00f6czky, K.J.: Finite Packing and Covering. Cambridge Tracts in Mathematics, vol. 154. Cambridge University Press, Cambridge (2004)","DOI":"10.1017\/CBO9780511546587"},{"issue":"4","key":"9872_CR7","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1007\/s00454-014-9594-5","volume":"51","author":"G Borradaile","year":"2014","unstructured":"Borradaile, G., Chambers, E.W.: Covering nearly surface-embedded graphs with a fixed number of balls. Discrete Comput. Geom. 51(4), 979\u2013996 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR8","unstructured":"Bousquet, N.: Hitting Sets: VC-dimension and Multicut. PhD thesis, Universit\u00e9 de Montpellier II (2013). https:\/\/tel.archives-ouvertes.fr\/tel-01012106"},{"issue":"12","key":"9872_CR9","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1016\/j.disc.2015.05.026","volume":"338","author":"N Bousquet","year":"2015","unstructured":"Bousquet, N., Thomass\u00e9, S.: VC-dimension and Erd\u0151s\u2013P\u00f3sa property. Discrete Math. 338(12), 2302\u20132317 (2015)","journal-title":"Discrete Math."},{"key":"9872_CR10","doi-asserted-by":"publisher","unstructured":"Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Grundlehren der Mathematischen Wissenschaften, vol. 319. Springer, Berlin (1999)","DOI":"10.1007\/978-3-662-12494-9"},{"issue":"4","key":"9872_CR11","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(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9872_CR12","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1016\/j.ejc.2009.03.045","volume":"31","author":"PJ Cameron","year":"2010","unstructured":"Cameron, P.J.: Problems from CGCS Luminy, May 2007. Eur. J. Combin. 31(2), 644\u2013648 (2010)","journal-title":"Eur. J. Combin."},{"issue":"1","key":"9872_CR13","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/s00454-014-9643-0","volume":"53","author":"J Chalopin","year":"2015","unstructured":"Chalopin, J., Chepoi, V., Naves, G.: Isometric embedding of Busemann surfaces into $$L_1$$ L 1 . Discrete Comput. Geom. 53(1), 16\u201337 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9872_CR14","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373\u2013392 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00454-006-1260-0","volume":"37","author":"V Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B., Vax\u00e8s, Y.: On covering planar graphs with a fixed number of balls. Discrete Comput. Geom. 37, 237\u2013244 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-540-74208-1_5","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"V Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B.: Packing and covering $$\\delta $$ \u03b4 -hyperbolic spaces by balls. In: Charikar, M., et al. (eds.) Approximation, Randomization, and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4627, pp. 59\u201373. Springer, Berlin (2007)"},{"issue":"9","key":"9872_CR17","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1016\/j.comgeo.2013.05.008","volume":"46","author":"V Chepoi","year":"2013","unstructured":"Chepoi, V., Felsner, S.: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46(9), 1036\u20131041 (2013)","journal-title":"Comput. Geom."},{"issue":"1","key":"9872_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"KL Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22(1), 63\u201393 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR19","doi-asserted-by":"publisher","unstructured":"Cornu\u00e9jols, G.: Combinatorial Optimization: Packing and Covering. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74. SIAM, Philadelphia (2001)","DOI":"10.1137\/1.9780898717105"},{"issue":"2","key":"9872_CR20","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/s00454-014-9661-y","volume":"53","author":"J Correa","year":"2015","unstructured":"Correa, J., Feuilloley, L., P\u00e9rez-Lantero, P., Soto, J.A.: Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity. Discrete Comput. Geom. 53(2), 344\u2013365 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR21","doi-asserted-by":"publisher","unstructured":"Dudley, R.M.: Uniform Central Limit Theorems. Cambridge Studies in Advanced Mathematics, vol. 63. Cambridge University Press, Cambridge (1999)","DOI":"10.1017\/CBO9780511665622"},{"issue":"2","key":"9872_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0012-365X(85)90045-7","volume":"55","author":"A Gy\u00e1rf\u00e1s","year":"1985","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: Covering and coloring problems for relatives of intervals. Discrete Math. 55(2), 167\u2013180 (1985)","journal-title":"Discrete Math."},{"key":"9872_CR23","unstructured":"Hadwiger, H., Debrunner, H.: Kombinatorische Geometrie in der Ebene. Monographies de \u201cL\u2019Enseignement Math\u00e9matique\u201d, No.\u00a02. Institut de Math\u00e9matiques, Universit\u00e9 Gen\u00e8ve, Gen\u00e8ve (1959)"},{"key":"9872_CR24","first-page":"109","volume":"21","author":"S Ivanov","year":"2014","unstructured":"Ivanov, S.: On Helly\u2019s theorem in geodesic spaces. Electron. Res. Announc. Math. Sci. 21, 109\u2013112 (2014)","journal-title":"Electron. Res. Announc. Math. Sci."},{"issue":"2\u20133","key":"9872_CR25","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s004540010040","volume":"24","author":"RN Karasev","year":"2000","unstructured":"Karasev, R.N.: Transversals for families of translates of a two-dimensional convex compact set. Discrete Comput. Geom. 24(2\u20133), 345\u2013353 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR26","first-page":"282","volume":"17","author":"AN Kolmogorov","year":"1961","unstructured":"Kolmogorov, A.N., Tihomirov, V.M.: $$\\varepsilon $$ \u03b5 -Entropy and $$\\varepsilon $$ \u03b5 -Capacity of sets in function spaces. Am. Math. Soc. Transl. 17, 282\u2013369 (1961)","journal-title":"Am. Math. Soc. Transl."},{"key":"9872_CR27","unstructured":"Kulkarni, S.R.: On Metric entropy, Vapnik\u2013Chervonenkis dimension, and learnability for a class of distributions. Technical Report 868 (1989). http:\/\/www.dtic.mil\/dtic\/tr\/fulltext\/2\/a217331"},{"issue":"6","key":"9872_CR28","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1090\/S0002-9904-1966-11586-0","volume":"72","author":"GG Lorentz","year":"1966","unstructured":"Lorentz, G.G.: Metric entropy and approximation. Bull. Am. Math. Soc. 72(6), 903\u2013937 (1966)","journal-title":"Bull. Am. Math. Soc."},{"issue":"4","key":"9872_CR29","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."},{"key":"9872_CR30","doi-asserted-by":"crossref","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1995)","DOI":"10.1002\/9781118033203"},{"key":"9872_CR31","doi-asserted-by":"crossref","unstructured":"Papadopoulos, A.: Metric Spaces, Convexity and Nonpositive Curvature. IRMA Lectures in Mathematics and Theoretical Physics, vol. 6. European Mathematical Society, Z\u00fcrich (2005)","DOI":"10.4171\/010"},{"issue":"6","key":"9872_CR32","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/BF02187751","volume":"4","author":"R Pollack","year":"1989","unstructured":"Pollack, R., Sharir, M., Rote, G.: Computing the geodesic center of a simple polygon. Discrete Comput. Geom. 4(6), 611\u2013626 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9872_CR33","unstructured":"Schrijver, A.: Combinatorial Optimization, Vol. B. Algorithms and Combinatorics, vol. 24.B. Springer, Berlin (2003)"},{"key":"9872_CR34","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"9872_CR35","unstructured":"Vigan, I.: Packing and covering a polygon with geodesic disks. http:\/\/arxiv.org\/abs\/1311.6033 (2013)"},{"issue":"4","key":"9872_CR36","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF03008396","volume":"3","author":"G Wegner","year":"1965","unstructured":"Wegner, G.: \u00dcber eine kombinatorisch-geometrische Frage von Hadwiger and Debrunner. Isr. J. Math. 3(4), 187\u2013198 (1965)","journal-title":"Isr. J. Math."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9872-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9872-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9872-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T11:57:45Z","timestamp":1601726265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9872-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["9872"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9872-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]}}}