Tight upper bounds for the discrepancy of half-spaces

We show that the discrepancy of anyn-point setP in the Euclideand-space with respect to half-spaces is bounded byC _d n ^1/2−1/2d , that is, a mapping χ:P→{−1,1} exists such that, for any half-space γ, γ, |Σ _p∈P⋂γ χ(p)|≤C _d n ^1/2-1/2d . In fact, the result holds for arbitrary set systems as long as theprimal shatter function isO(m ^d ). This matches known lower bounds, improving previous upper bounds by a factor. Part of this research was done at the Third Israeli Computational Geometry Workshop in Ramot and during a visit at Tel Aviv University in December 1993. Also supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167.