Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n^1/2–1/2d(logn)^1+1/2d). Also if any subcollection ofm sets of partitions the points into at mostO(m^d) classes, then there is a coloring with discrepancy at mostO(n^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.