On the Discrepancy for Cartesian Products

Let B₂ denote the family of all circular discs in the plane.It is proved that the discrepancy for the family {B₁ x B₂ :B₁, B₂ B₂} in R⁴ is O(n^1/4+) for an arbitrarily small constant > 0, that is, it is essentially the same as that for thefamily B₂ itself. The result is established for the combinatorialdiscrepancy, and consequently it holds for the discrepancy withrespect to the Lebesgue measure as well. This answers a questionof Beck and Chen. More generally, we prove an upper bound forthe discrepancy for a family {^k_i=1A_i:A_iA_i, i = 1, 2, ..., k},where each A_i is a family in R^d_i, each of whose sets is describedby a bounded number of polynomial inequalities of bounded degree.The resulting discrepancy bound is determined by the ‘worst’of the families A_i, and it depends on the existence of certaindecompositions into constant-complexity cells for arrangementsof surfaces bounding the sets of A_i. The proof uses Beck's partialcoloring method and decomposition techniques developed for therange-searching problem in computational geometry.