## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 519-524 |

Number of pages | 6 |

Journal | Discrete and Computational Geometry |

Volume | 25 |

Issue number | 4 |

DOIs | |

State | Published - Jun 2001 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics