Quasi-Orthogonality via Finite-Differencing: An Elementary Approach to Geometric Discrepancy

Abstract:

It is possible to place n points in d-space so that, given any
two-coloring of the points, there exists a halfspace within which one
color dominates the other by as much as c n^{1/2- 1/2d} , for some
constant c >0. This result was proven in a slightly weaker form by
Beck and the bound was later tightened by Alexander. It was shown to
be quasi-optimal by Matou&scheck;ek, Welzl, and Wernisch. The lower
bound proofs are highly technical and do not provide much intuitive
insight into the ``large-discrepancy'' phenomenon. We develop a proof
technique which allows us to rederive the same lower bound in a much
simpler fashion. We give a probabilistic interpretation of the result
and we discuss the connection of our method to Beck's Fourier
transform approach. We also provide a quasi-optimal lower bound on
the discrepancy of fixed-size rotated boxes, which significantly
improves the previous bound.