AN ELEMENTARY APPROACH TO LOWER BOUNDS IN GEOMETRIC DISCREPANCY

Citation
B. Chazelle et al., AN ELEMENTARY APPROACH TO LOWER BOUNDS IN GEOMETRIC DISCREPANCY, Discrete & computational geometry, 13(3-4), 1995, pp. 363-381
Citations number
11
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
ISSN journal
01795376
Volume
13
Issue
3-4
Year of publication
1995
Pages
363 - 381
Database
ISI
SICI code
0179-5376(1995)13:3-4<363:AEATLB>2.0.ZU;2-R
Abstract
For each d greater than or equal to 2, it is possible to place n point s in d-space so that, given any two-coloring of the points, a half-spa ce exists within which one color outnumbers the other by as much as Cn (1/2-1/2d), for some constant c > 0 depending on d. This result was pr oven in a slightly weaker form by Beck and the bound was later tighten ed by Alexander. It was recently shown to be asymptotically optimal by MatouSek. We present a proof of the lower bound, which is based on Al exander's technique but is technically simpler and more accessible. We present three variants of the proof, for three different cases, to pr ovide more intuitive insight into the ''large-discrepancy'' phenomenon . We also give geometric and probabilistic interpretations of the tech nique.