Geometric discrepancy. An illustrated guide
Alexander's methodapplications to numerical integrationBeck's Fourier transform approachBeck-Fiala theoremcircular discscombinatorial discrepancydiscrepancyentropy methodexercisesintroductory textbooklow discrepancy sequenceslower bounds for geometric discrepanciespartial coloring methodquasi Monte-Carlo methodsSpencer's upper boundtable of selected discrepancy boundsuniform distributionupper boundVapnik-Chervonenkis dimension
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.
- Geometric discrepancy. An illustrated guide
- Discrepancy theory
- 1. On some recent developments in uniform distribution and discrepancy theory
- Sequences, discrepancies and applications
- scientific article; zbMATH DE number 863495
- Number theory, Fourier analysis and geometric discrepancy
- The ``Great Year of the Kronecker sequence
- scientific article; zbMATH DE number 5528958
- Discrepancy theory and its applications
- Evaluation of the discrepancy of the linear congruential pseudo-random number sequences
- Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
- Asymptotically optimal declustering schemes for 2-dim range queries.
- Cubature formulas, discrepancy, and nonlinear approximation
- Some open problems concerning the star-discrepancy
- The Kadison-Singer problem in discrepancy theory.
- On ordered Ramsey numbers of bounded-degree graphs
- Universal discretization
- BMO and exponential Orlicz space estimates of the discrepancy function in arbitrary dimension
- Optimal \(L_{p}\)-discrepancy bounds for second order digital sequences
- A note on minimal dispersion of point sets in the unit cube
- Optimal jittered sampling for two points in the unit square
- Tractability properties of the weighted star discrepancy of the Halton sequence
- On the number of maximum empty boxes amidst \(n\) points
- Discrepancy theory and its applications
- Smooth fixed volume discrepancy, dispersion, and related problems
- Typical rounding problems
- \(I\)-binomial scrambling of digital nets and sequences
- On the root mean square weighted \(L_{2}\) discrepancy of scrambled nets
- Geometric characterization of Weyl's discrepancy norm in terms of its \(n\)-dimensional unit balls
- On the largest empty axis-parallel box amidst \(n\) points
- On the fixed volume discrepancy of the Fibonacci sets in the integral norms
- An exact formula for the L₂ discrepancy of the symmetrized Hammersley point set
- On an explicit lower bound for the star discrepancy in three dimensions
- Sorting methods and convergence rates for Array-RQMC: some empirical comparisons
- Discrepancy of stratified samples from partitions of the unit cube
- Rainbow polygons for colored point sets in the plane
- Bounds for discrepancies in the Hamming space
- The VC-dimension of axis-parallel boxes on the torus
- Gaussian discrepancy: a probabilistic relaxation of vector balancing
- Numerical integration and discrepancy under smoothness assumption and without it
- Geometric systems of unbiased representatives
- Optimal approximations made easy
- Positive definiteness and the Stolarsky invariance principle
- Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
- Powers of Hamilton cycles of high discrepancy are unavoidable
- The \(\varepsilon\)-\(t\)-net problem
- Connections between numerical integration, discrepancy, dispersion, and universal discretization
- Bisecting and \(D\)-secting families for set systems
- An enumerative formula for the spherical cap discrepancy
- Discrepancy norm: approximation and variations
- Extremal distributions of discrepancy functions
- A nonlocal functional promoting low-discrepancy point sets
- Approximating a planar convex set using a sparse grid
- Online uniformly inserting points on the sphere
- When are epsilon-nets small?
- Compositional falsification of cyber-physical systems with machine learning components
- Discrepancy theory
- On small \(n\)-uniform hypergraphs with positive discrepancy
- The chromatic discrepancy of graphs
- The test suite generation problem: optimal instances and their implications
- Scrambled geometric net integration over general product spaces
- Spectrally optimized pointset configurations
- The Stolarsky principle and energy optimization on the sphere
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- On lower bounds for the \(L_2\)-discrepancy
- Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension
- A metrical lower bound on the star discrepancy of digital sequences
- Minimum-link paths revisited
- Optimization-based design of plant-friendly multisine signals using geometric discrepancy criteria
- Quantum lower bounds by entropy numbers
- Non-independent randomized rounding and coloring
- Improved bounds and schemes for the declustering problem
- Control variates for quasi-Monte Carlo (with comments and rejoinder)
- Discrepancy of (centered) arithmetic progressions in \({\mathbb{Z}_p}\)
- Constructions of (t,m,s)-nets and (t,s)-sequences
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- On the necessity of low-effective dimension
- A semi-algebraic version of Zarankiewicz's problem
- Discrepancy bounds for infinite-dimensional order two digital sequences over \(\mathbb F_2\)
- On the discrepancy of circular sequences of reals
- Discrepancies of spanning trees and Hamilton cycles
- The nonzero gain coefficients of Sobol's sequences are always powers of two
- The BMO-discrepancy suffers from the curse of dimensionality
- Optimal periodic L₂-discrepancy and diaphony bounds for higher order digital sequences
- Applications of geometric discrepancy in numerical analysis and statistics
- Better bin packing approximations via discrepancy theory
- Discrepancy of high-dimensional permutations
- The Khinchin inequality and Chen's theorem
- Discrepancy of centered arithmetic progressions in \(\mathbb{Z}_p\) (extended abstract)
- Uniformity of point samples in metric spaces using gap ratio
- Two dimensional range minimum queries and Fibonacci lattices
- Constructive Discrepancy Minimization for Convex Sets
- Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions
- Exponential convergence and tractability of multivariate integration for Korobov spaces
- Point sets with low L p-discrepancy
- Discrepancy of Sums of Arithmetic Progressions
- Constructive discrepancy minimization by walking on the edges
- Discrepancy of Sums of two Arithmetic Progressions
- On the exponent of discrepancies
- Comparison of Point Sets and Sequences for Quasi-Monte Carlo and for Random Number Generation
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- scientific article; zbMATH DE number 1512071 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- One-sided epsilon-approximants
- Finding exact formulas for the L₂ discrepancy of digital (0,n,2)-nets via Haar functions
- Discrepancy estimates for index-transformed uniformly distributed sequences
- Intersections of hypergraphs
- scientific article; zbMATH DE number 863495 (Why is no real title available?)
- Lower bounds for the number of hyperplanes separating two finite sets of points
- The Communication Complexity of Distributed epsilon-Approximations
This page was built for publication: Geometric discrepancy. An illustrated guide
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906395)
