Quasi-Orthogonality via Finite-Differencing: An Elementary Approach to Geometric Discrepancy
Report ID: TR-407-93Author: Chazelle, Bernard
Date: 1993-02-00
Pages: 13
Download Formats: |Postscript|
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.