An elementary approach to lower bounds in geometric discrepancy
Given a set of points in \(d\)-space, I color them red or blue, after which you will select a half-space, containing \(R\) red points and \(B\) blue points. Your goal is to maximize \(|R - B|\); mine is to foce it to be small. Geometric discrepancy theory tells us that there exist sets upon which you can always do rather well at this game. In fact, if we start with a favorable set of \(n\) points, a theorem of Alexander guarantees you a discrepancy of at least \[ c(d) \cdot n^{1/2 - 1/2d}, \] and the second author has shown that this is asymptotically optimal. This paper presents some alternative, more elementary, proofs of Alexander's theorem, and related results. There is a particularly nice proof of the planar case, by probabilistic methods. The author's efforts to motivate their proofs make this a particularly enjoyable and enlightening paper to read, even for the nonspecialist.
- Discrepancy and approximations for bounded VC-dimension
- Geometric methods in the study of irregularities of distribution
- scientific article; zbMATH DE number 3653400 (Why is no real title available?)
- scientific article; zbMATH DE number 3533716 (Why is no real title available?)
- scientific article; zbMATH DE number 4000052 (Why is no real title available?)
- Principles of a new method in the study of irregularities of distribution
- Quasi‐random 2‐ colorings of point sets
- Remark concerning integer sequences
- Tight upper bounds for the discrepancy of half-spaces
This page was built for publication: An elementary approach to lower bounds in geometric discrepancy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892416)
