© 2000 by London Mathematical Society
© The London Mathematical Society
On the Discrepancy for Cartesian Products
í Matou
ekDepartment of Applied Mathematics, Charles University Malostranské nám. 25, 118 00 Praha 1, Czech Republic, matousek{at}kam.mff.cuni.cz
Received 12 July 1998.
Let B2 denote the family of all circular discs in the plane. It is proved that the discrepancy for the family {B1 x B2 : B1, B2 
B2} in R4 is O(n1/4+
) for an arbitrarily small constant > 0, that is, it is essentially the same as that for the family B2 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:AiAi, 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.