Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-407-93
Quasi-Orthogonality via Finite-Differencing: An Elementary Approach to Geometric Discrepancy
Authors: Chazelle, Bernard
Date:February 1993
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.