Abstract
We show that the discrepancy of anyn-point setP in the Euclideand-space with respect to half-spaces is bounded byC d n 1/2−1/2d, that is, a mapping χ:P→{−1,1} exists such that, for any half-space γ, γ, |Σ p∈P⋂γ χ(p)|≤C d n 1/2-1/2d. In fact, the result holds for arbitrary set systems as long as theprimal shatter function isO(m d). This matches known lower bounds, improving previous upper bounds by a\(\sqrt {\log n} \) factor.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
[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–300, 1993.
[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–38.
[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–340, 1987.
[Al] R. Alexander. Geometric methods in the theory of uniform distribution.Combinatorica, 10(2):115–136, 1990.
[AS] N. Alon and J. Spencer.The Probabilistic Method. Wiley, New York, 1993.
[BC] J. Beck and W. Chen.Irregularities of Distribution. Cambridge University Press, Cambridge, 1987.
[BCM] H. Brönnimann, B. Chazelle, and J. Matoušek. Product range spaces, sensitive sampling and derandomization.Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pages 400–409.
[Be] J. Beck. Roth's estimate on the discrepancy of integer sequences is nearly sharp.Combinatorica 1(4):319–325, 1981.
[BS] J. Beck and V. Sós. Discrepancy theory.Handbook of Combinatorics, North-Holland, Amsterdam, to appear.
[Ch] B. Chazelle. Geometric discrepancy revisited.Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993, pages 392–399.
[CW] B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension.Discrete Comput. Geom., 4:467–489, 1989.
[Ed] H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, Vol. 10. Springer-Verlag, Heidelberg, 1987.
[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.
[HW] D. Haussler and E. Welzl. Epsilon-nets and simplex range queries.Discrete Comput. Geom., 2:127–151, 1987.
[Ma] J. Matoušek. Geometric range searching.ACM Comput. Surrveys, to appear.
[Mu] K. Mulmuley.Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, New York, 1993.
[MWW] J. Matoušek, E. Welzl, and L. Wernisch. Discrepancy and ε-approximations for bounded VC-dimension.Combinatorica, 13:455–466, 1993.
[Sp] J. Spencer. Six standard deviations suffice.Trans. Amer. Math. Soc., 289:679–706, 1985.
[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–280, 1971.
[We] L. Wernisch. Note on stabbing numbers and sphere packing. Manuscript, Computer Science Institute, Free University Berlin, 1992.
Author information
Authors and Affiliations
Additional information
Part of this research was done at the Third Israeli Computational Geometry Workshop in Ramot and during a visit at Tel Aviv University in December 1993. Also supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167.
Rights and permissions
About this article
Cite this article
Matoušek, J. Tight upper bounds for the discrepancy of half-spaces. Discrete Comput Geom 13, 593–601 (1995). https://doi.org/10.1007/BF02574066
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574066