{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T21:38:29Z","timestamp":1725831509096},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319244853"},{"type":"electronic","value":"9783319244860"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24486-0_15","type":"book-chapter","created":{"date-parts":[[2015,10,3]],"date-time":"2015-10-03T21:20:50Z","timestamp":1443907250000},"page":"224-238","source":"Crossref","is-referenced-by-count":2,"title":["Subsampling in Smoothed Range Spaces"],"prefix":"10.1007","author":[{"given":"Jeff M.","family":"Phillips","sequence":"first","affiliation":[]},{"given":"Yan","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,10,31]]},"reference":[{"key":"15_CR1","unstructured":"Fitzgibbon, A., Bergamo, A., Torresani, L.: Picodes: learning a compact code for novel-category recognition. In: NIPS (2011)"},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/263867.263927","volume":"44","author":"N Alon","year":"1997","unstructured":"Alon, N., Ben-David, S., Cesa-Bianchi, N., Haussler, D.: Scale-sensitive dimensions, uniform convergence, and learnability. Journal of ACM 44, 615\u2013631 (1997)","journal-title":"Journal of ACM"},{"key":"15_CR3","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 $$\\varepsilon $$ -nets for axis-parallel rectangles and boxes. Siam Journal of Computing 39, 3248\u20133282 (2010)","journal-title":"Siam Journal of Computing"},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02392553","volume":"159","author":"J Beck","year":"1987","unstructured":"Beck, J.: Irregularities of distribution I. Acta Mathematica 159, 1\u201349 (1987)","journal-title":"Acta Mathematica"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Bern, M., Eppstein, D.: Worst-case bounds for subadditive geometric graphs. In: SOCG (1993)","DOI":"10.1145\/160985.161018"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: The Discrepancy Method. Cambridge (2000)","DOI":"10.1017\/CBO9780511626371"},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Matousek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimensions. J. Algorithms 21, 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge (2009)","DOI":"10.1017\/CBO9780511581274"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canadian Journal of Mathematics 17, 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"15_CR10","unstructured":"Har-Peled, S., Kaplan, H., Sharir, M., Smorodinksy, S.: $$\\varepsilon $$ -nets for halfspaces revisited. Technical report (2014). arXiv:1410.3154"},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: epsilon-nets and simplex range queries. Disc. & Comp. Geom. 2, 127\u2013151 (1987)","journal-title":"Disc. & Comp. Geom."},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Joshi, S., Kommaraju, R.V., Phillips, J.M., Venkatasubramanian, S.: Comparing distributions and shapes using the kernel distance. In: SOCG (2011)","DOI":"10.1145\/1998196.1998204"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Larsen, K.G.: On range searching in the group model and combinatorial discrepancy. In: FOCS (2011)","DOI":"10.1109\/FOCS.2011.14"},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1006\/jcss.2000.1741","volume":"62","author":"Y Li","year":"2001","unstructured":"Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the samples complexity of learning. J. Comp. and Sys. Sci. 62, 516\u2013527 (2001)","journal-title":"J. Comp. and Sys. Sci."},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/BF02574066","volume":"13","author":"J Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: Tight upper bounds for the discrepancy of halfspaces. Discrete & Computational Geometry 13, 593\u2013601 (1995)","journal-title":"Discrete & Computational Geometry"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy. Springer (1999)","DOI":"10.1007\/978-3-642-03942-3"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Seidel, R., Welzl, E.: How to net a lot with little: small $$\\varepsilon $$ -nets for disks and halfspaces. In: SOCG (1990)","DOI":"10.1145\/98524.98530"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial geometry. Wiley, Wiley-Interscience series in discrete mathematics and optimization (1995)","DOI":"10.1002\/9781118033203"},{"key":"15_CR19","doi-asserted-by":"crossref","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. Journal of American Mathematical Society 26, 645\u2013658 (2013)","journal-title":"Journal of American Mathematical Society"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Phillips, J.M.: Algorithms for $$\\varepsilon $$ -approximations of terrains. In: Automata, Languages and Programming, pp. 447\u2013458. Springer (2008)","DOI":"10.1007\/978-3-540-70575-8_37"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Phillips, J.M.: Eps-samples for kernels. In: SODA (2013)","DOI":"10.1137\/1.9781611973105.116"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Pollard, D.: Emperical processes: theory and applications. In: NSF-CBMS REgional Confernece Series in Probability and Statistics (1990)","DOI":"10.1214\/cbms\/1462061091"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Pyrga, E., Ray, S.: New existence proofs $$\\varepsilon $$ -nets. In: SOCG (2008)","DOI":"10.1145\/1377676.1377708"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Vapnik, V.: Inductive principles of the search for empirical dependencies. In: COLT (1989)","DOI":"10.1016\/B978-0-08-094829-4.50004-0"},{"key":"15_CR25","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V Vapnik","year":"1971","unstructured":"Vapnik, V., Chervonenkis, A.: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications 16, 264\u2013280 (1971)","journal-title":"Theory of Probability and its Applications"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Varadarajan, K.R.: A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: FOCS (1998)","DOI":"10.1109\/SFCS.1998.743466"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24486-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,22]],"date-time":"2022-05-22T16:58:53Z","timestamp":1653238733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24486-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319244853","9783319244860"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24486-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}