The discrepancy of boxes in higher dimension

We prove that the red-blue discrepancy of the set system formed by n points and n axis-parallel boxes in R-d can be as high as n(Omega (1)) in any dim ension d = Omega (log n). This contrasts with the fixed-dimensional case d = O(1), where the discrepancy is always polylogarithmic. Mure generally we show that in any dimension 1 < d = O(log n) the maximum discrepancy is 2(Om ega (d)). Our result also leads to a new lower bound on the complexity of o ff-line orthogonal range searching. This: is: the problem of summing up wei ghts in boxes, given n weighted points and n boxes in R-d. We prove that th e number of arithmetic operations is at least Omega (nd + n log log n) in a ny dimension d = O (log n).