Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-407-93

Authors:

Date:

January 1993

Pages:

13

Download Formats:

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 asc n^{1/2- 1/2d}, for some

constantc>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.