Upper Bounds in the Lebesgue-Measure Setting

In this chapter we start proving upper bounds for the discrepancy for objects other than the axis-parallel boxes. We will encounter a substantially different behavior of the discrepancy function, already mentioned in Section 1.2. For axis-parallel boxes, the discrepancy is at most of a power of log n, and similar results can be shown, for example, for homothets of a fixed convex polygon. The common feature is that the directions of the edges are fixed. It turns out that if we allow arbitrary rotation of the objects, or if we consider objects with a curved boundary, discrepancy grows as some fractional power of n. The simplest such class of objects is the set H₂ of all (closed) halfplanes, for which the discrepancy function D(n,H₂) is of the order n1/4. For halfspaces in higher dimensions, the discrepancy is of the order n1/2−1/2d; so the exponent approaches 1/2 as the dimension grows. Other classes of “reasonable” geometric objects, such as all balls in Rd, all cubes (with rotation allowed), all ellipsoids, etc., exhibit a similar behavior. The discrepancy is again roughly n1/2−4/2d although there are certain subtle differences.