An elementary approach to lower bounds in geometric discrepancy |
| |
Authors: | B Chazelle J Matou?ek M Sharir |
| |
Institution: | (1) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(2) Department of Applied Mathematics, Charles University, 11800 Praha 1, Czech Republic;(3) School of Mathematical Sciences, Tel Aviv University, 69 978 Ramat Aviv, Israel;(4) Courant Institute of Mathematical Sciences, New York University, 10012 New York, NY, USA |
| |
Abstract: | For eachd≥2, it is possible to placen points ind-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as
much ascn
1/2−1/2d
, for some constantc>0 depending ond. 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.
Work by Bernard Chazelle has been supported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota,
an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Jiří Matoušek has been supported by Charles University Grant
No. 351, by Czech Republic Grant GAČR 201/93/2167 and in part by DIMACS. Work by Micha Sharir has been supported by NSF Grant
CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund
for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific
Research and Development. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|