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^Ω(1) in any dimension d = Ω (log n). This contrasts with the fixed-dimensional case d = O(1), where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1 < d = O(log n) the maximum discrepancy is 2^Ω(d). Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in R^d. We prove that the number of arithmetic operations is at least Ω(nd + n log log n) in any dimensions d = O(log n).