The discrepancy of boxes in higher dimension

B. Chazelle, A. Lvov

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)519-524
Number of pages6
JournalDiscrete and Computational Geometry
Volume25
Issue number4
DOIs
StatePublished - Jun 2001

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'The discrepancy of boxes in higher dimension'. Together they form a unique fingerprint.

  • Cite this