Geometric discrepancy and range spaces

Let X be a finite set of n points, and let a family of geometric regions induce subsets R ∩ X, called ranges or traces. A coloring χ assigns either plus one or minus one to each point. The signed sum over a range is its color imbalance, and the discrepancy of the coloring is the largest absolute imbalance among all ranges. The discrepancy of the range space minimizes that worst-case quantity over all colorings.

Only distinct traces matter, even when infinitely many geometric regions produce them. For a fixed finite X there are finitely many possible traces. This formulation is combinatorial discrepancy, distinct from star discrepancy, which compares uncolored sample proportions with a reference volume measure. Both study unevenness, but their inputs and normalizations differ. A bound for random sampling error is not automatically a theorem about a best two-coloring of a fixed point set.

For distinct points on the real line, color them alternately in sorted order. Every interval selects a consecutive block, so the positive and negative colors cancel in pairs and leave imbalance at most one. If the family contains all intervals and X is nonempty, singleton ranges force discrepancy at least one, proving the bound is exact. No probability is needed; the geometry supplies an order compatible with every range.

The same idea does not automatically work in higher dimensions, where a single sorted order need not make every disk or halfspace a consecutive block. For the family containing every subset, a fixed coloring has worst imbalance equal to the size of its larger color class: selecting all points of that color attains it, and no subset can exceed it. The optimum is therefore ceiling(n/2), attained by balancing the two class sizes as evenly as possible. The latter exact value shows why one must compute the worst range carefully rather than confusing it with the signed sum over the entire set.

Choose independent unbiased signs. For a fixed range with k points, an exponential tail bound gives probability at most 2 exp(−u²/(2k)) for absolute imbalance exceeding u. Replacing k by n and applying a union bound over M nonempty distinct traces shows that u = square root of 2n log(4M) succeeds for all ranges with probability at least one-half. Thus some coloring achieves that bound, though geometry may allow much smaller discrepancy.

A subset is shattered when every one of its subsets occurs as a trace, and VC dimension is the largest size of a shattered subset. For a range family of VC dimension v, the Sauer–Shelah counting lemma bounds the number of distinct traces on n points by the sum of binomial coefficients through v, with v at most n. We state that lemma rather than prove it here. For fixed v, polynomial trace complexity turns the generic random bound into a square-root-n logarithmic estimate, but this does not prove the optimal geometric rate. Interval ranges already show the gap: random-sign reasoning gives a growing bound while the deterministic alternating construction gives one.