An introduction to discrepancy theory

Abstract

This paper introduces the basic elements of geometric discrepancy theory. After some background we discuss lower bounds for two problems, Schmidt’s theorem giving a lower bound for convex sets and Roth’s orthogonal method for the lower bound of the L₂ discrepancy of axis-parallel rectangles in the unit square. Then we introduce two sets with low worst-case discrepancy, the Van der Corput set for two dimensions and the Halton-Hammersley set for arbitrary dimension.