An elementary approach to lower bounds in geometric discrepancy

B. Chazelle, J. Matoušek, M. Sharir

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

For each d≥2, it is possible to place n points in d-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as much as cn 1/2-1/2 d, for some constant c>0 depending on d. This result was proven in a slightly weaker form by Beck and the bound was later tightened by Alexander. It was recently shown to be asymptotically optimal by Matoušek. We present a proof of the lower bound, which is based on Alexander's technique but is technically simpler and more accessible. We present three variants of the proof, for three diffrent cases, to provide more intuitive insight into the "large-discrepancy" phenomenon. We also give geometric and probabilistic interpretations of the technique.

Original languageEnglish (US)
Pages (from-to)363-381
Number of pages19
JournalDiscrete & Computational Geometry
Volume13
Issue number1
DOIs
StatePublished - Dec 1 1995

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 'An elementary approach to lower bounds in geometric discrepancy'. Together they form a unique fingerprint.

  • Cite this