On the discrepancy for Cartesian products

Let B 2 denote the family of all circular discs in the plane. We prove that the discrepancy for the family fB 1 \Theta B 2 : B 1 ; B 2 2 B 2 g in R 4 is O(n 1=4+" ) for an arbitrarily small constant " ? 0, i.e. essentially the same as that for the family B 2 itself. The result is established for the combinatorial discrepancy, and consequently it holds for the discrepancy with respect to the Lebesgue measure as well. This answers a question of Beck and Chen. More generally, we prove an upper bound for the discrepancy for a family f Q k i=1 A i : A i 2 A i ; i = 1; 2; : : : ; kg, where each A i is a family in R d i , each of whose sets is described by a bounded number 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 certain decompositions into constant-complexity cells for arrangements of surfaces bounding the sets of A i . The proof uses Beck's partial coloring method ..