An elementary approach to lower bounds in geometric discrepancy (Q1892416)

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.