We prove that the red-blue discrepancy of the set system formed by n points and n axis-parallel boxes in Rd' 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 Rd. We prove that the number of arithmetic operations is at least Ω(nd + n log log n) in any dimensions d = O(log n).
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics