Published online by Cambridge University Press: 01 June 2000
Let [Bscr ]2 denote the family of all circular discs in the plane. It is proved that the discrepancy for the family {B1 × B2 [ratio ] B1, B2 ∈ [Bscr ]2} in R4 is O(n1/4+ε) for an arbitrarily small constant ε > 0, that is, it is essentially the same as that for the family [Bscr ]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 {Πki=1Ai[ratio ] Ai∈Ai, i = 1, 2, …, k}, where each Ai is a family in Rdi, each of whose sets is described by a bounded number of polynomial inequalities of bounded degree. The resulting discrepancy bound is determined by the ‘worst’ of the families Ai , and it depends on the existence of certain decompositions into constant-complexity cells for arrangements of surfaces bounding the sets of Ai. The proof uses Beck's partial coloring method and decomposition techniques developed for the range-searching problem in computational geometry.