{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T20:08:32Z","timestamp":1790366912385,"version":"4.1.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf02574066","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:15:26Z","timestamp":1174565726000},"page":"593-601","source":"Crossref","is-referenced-by-count":38,"title":["Tight upper bounds for the discrepancy of half-spaces"],"prefix":"10.1007","volume":"13","author":[{"given":"J.","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1995,6,1]]},"reference":[{"key":"BF02574066_CR1","doi-asserted-by":"crossref","unstructured":"[ABCH] N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimension, uniform convergence and learnability.Proc. 34th IEEE Symposium on Foundations of Computer Science, pages 292\u2013300, 1993.","DOI":"10.1109\/SFCS.1993.366858"},{"key":"BF02574066_CR2","first-page":"1","volume-title":"Computational Geometry: Papers from the DIMACS Special Year","author":"P.K. Agarwal","year":"1991","unstructured":"[Ag] P.K. Agarwal. Geometric partitioning and its applications. In J.E. Goodman, R. Pollack, and W. Steiger, editors,Computational Geometry: Papers from the DIMACS Special Year. American Mathematical Society, Providence, RI, 1991, pages 1\u201338."},{"key":"BF02574066_CR3","doi-asserted-by":"crossref","unstructured":"[AHW] N. Alon, D. Haussler, and E. Welzl. Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension.Proc. 3rd ACM Symposium on Computational Geometry, pages 331\u2013340, 1987.","DOI":"10.1145\/41958.41994"},{"issue":"2","key":"BF02574066_CR4","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02123006","volume":"10","author":"R. Alexander","year":"1990","unstructured":"[Al] R. Alexander. Geometric methods in the theory of uniform distribution.Combinatorica, 10(2):115\u2013136, 1990.","journal-title":"Combinatorica"},{"key":"BF02574066_CR5","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1993","unstructured":"[AS] N. Alon and J. Spencer.The Probabilistic Method. Wiley, New York, 1993."},{"key":"BF02574066_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511565984","volume-title":"Irregularities of Distribution","author":"J. Beck","year":"1987","unstructured":"[BC] J. Beck and W. Chen.Irregularities of Distribution. Cambridge University Press, Cambridge, 1987."},{"key":"BF02574066_CR7","doi-asserted-by":"crossref","unstructured":"[BCM] H. Br\u00f6nnimann, B. Chazelle, and J. Matou\u0161ek. Product range spaces, sensitive sampling and derandomization.Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pages 400\u2013409.","DOI":"10.1109\/SFCS.1993.366847"},{"issue":"4","key":"BF02574066_CR8","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF02579452","volume":"1","author":"J. Beck","year":"1981","unstructured":"[Be] J. Beck. Roth's estimate on the discrepancy of integer sequences is nearly sharp.Combinatorica 1(4):319\u2013325, 1981.","journal-title":"Combinatorica"},{"key":"BF02574066_CR9","unstructured":"[BS] J. Beck and V. S\u00f3s. Discrepancy theory.Handbook of Combinatorics, North-Holland, Amsterdam, to appear."},{"key":"BF02574066_CR10","doi-asserted-by":"crossref","unstructured":"[Ch] B. Chazelle. Geometric discrepancy revisited.Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pages 392\u2013399.","DOI":"10.1109\/SFCS.1993.366848"},{"key":"BF02574066_CR11","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"[CW] B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension.Discrete Comput. Geom., 4:467\u2013489, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574066_CR12","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"[Ed] H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, Vol. 10. Springer-Verlag, Heidelberg, 1987."},{"key":"BF02574066_CR13","unstructured":"[Ha] D. Haussler. Sphere packing numbers for subsets of the Booleann-cube with bounded Vapnik-Chervonenkis dimension. Tech. Report UCSC-CRL-91-41, University of California at Santa Cruz, 1991. Also to appear inJ. Combin. Theory Ser. A."},{"key":"BF02574066_CR14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"[HW] D. Haussler and E. Welzl. Epsilon-nets and simplex range queries.Discrete Comput. Geom., 2:127\u2013151, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574066_CR15","doi-asserted-by":"crossref","unstructured":"[Ma] J. Matou\u0161ek. Geometric range searching.ACM Comput. Surrveys, to appear.","DOI":"10.1145\/197405.197408"},{"key":"BF02574066_CR16","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1993","unstructured":"[Mu] K. Mulmuley.Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, New York, 1993."},{"key":"BF02574066_CR17","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/BF01303517","volume":"13","author":"J. Matou\u0161ek","year":"1993","unstructured":"[MWW] J. Matou\u0161ek, E. Welzl, and L. Wernisch. Discrepancy and \u03b5-approximations for bounded VC-dimension.Combinatorica, 13:455\u2013466, 1993.","journal-title":"Combinatorica"},{"key":"BF02574066_CR18","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1090\/S0002-9947-1985-0784009-0","volume":"289","author":"J. Spencer","year":"1985","unstructured":"[Sp] J. Spencer. Six standard deviations suffice.Trans. Amer. Math. Soc., 289:679\u2013706, 1985.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF02574066_CR19","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"[VC] V.N. Vapnik and A.Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities.Theory Probab. Appl., 16:264\u2013280, 1971.","journal-title":"Theory Probab. Appl."},{"key":"BF02574066_CR20","unstructured":"[We] L. Wernisch. Note on stabbing numbers and sphere packing. Manuscript, Computer Science Institute, Free University Berlin, 1992."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574066.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574066\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:19:19Z","timestamp":1558196359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":20,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF02574066"],"URL":"https:\/\/doi.org\/10.1007\/bf02574066","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}