Geometric discrepancy. An illustrated guide (Q5906395): Difference between revisions

The present book is an introductory textbook on discrepancy theory focusing on combinatorial aspects. The book gives a very good introduction into the most important methods of the field (harmonic analysis, elementary number theory, probability theory and the probabilistic method in combinatorics, counting and asymptotic estimates, finite fields, algorithm design) as well as a survey on recent results. For general and more analytic aspects of discrepancy theory and for a detailed bibliography see the monograph by \textit{M. Drmota} and \textit{R. F. Tichy} [Sequences discrepancies and applications. Lecture Notes in Mathematics, Vol. 1651 (Springer 1997; Zbl 0877.11043)]. For an introduction into the theory of uniformly distributed sequences we refer to the monographs by \textit{L. Kuipers} and \textit{H. Niederreiter} [Uniform distribution of sequences (J. Wiley and Sons 1974; Zbl 0281.10001)] and by \textit{E. Hlawka} [Theorie der Gleichverteilung (Bibliographisches Institut 1979; Zbl 0406.10001)]. Chapter 1 is devoted to the discussion of the basic concepts of discrepancy theory: dicrepancy with respect to rectangles and uniform distribution, more general geometric and combinatorial concepts of discrepancy, applications to numerical integration and quasi Monte-Carlo methods. Chapter 2 contains various constructions of low discrepancy sequences including sequences of the net-type. For more details on such constructions see \textit{H. Niederreiter} [Doc. Math., J. DMV, Extra Vol. ICM Berlin 1998 vol. III, 377-386 (1998; Zbl 0899.11038)]. In Chapter 3 an upper bound for the discrepancy with respect to circular discs is established. Chapter 4 contains various problems in combinatorial discrepancy theory. Here, Spencer's upper bound and the Beck-Fiala theorem are shown. Furthermore, the partial coloring method and the entropy method are discussed. In Chapter 5 the author considers the Vapnik-Chervonenkis dimension and related discrepancy problems. Chapter 6 is devoted to various lower bounds for geometric discrepancies, including Alexander's method for the discrepancy with respect to half spaces. Chapter 7 gives an introduction to Beck's Fourier transform approach. The book concludes with a table of selected discrepancy bounds and with a list of references. Each chapter contains a collection of useful and interesting exercises and comments on the recent literature.