Geometric discrepancy. An illustrated guide

Publication date: 5 July 1999

Published in: Algorithms and Combinatorics (Search for Journal in Brave)

upper bound discrepancy entropy method uniform distribution low discrepancy sequences Vapnik-Chervonenkis dimension exercises combinatorial discrepancy applications to numerical integration circular discs Alexander's method Beck-Fiala theorem Beck's Fourier transform approach introductory textbook lower bounds for geometric discrepancies partial coloring method quasi Monte-Carlo methods Spencer's upper bound table of selected discrepancy bounds

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory (11-01) Irregularities of distribution, discrepancy (11K38) Extremal combinatorics (05D99)

Related Items

Uniformity of Point Samples in Metric Spaces Using Gap Ratio, Exponential convergence and tractability of multivariate integration for Korobov spaces, Constructive Discrepancy Minimization by Walking on the Edges, Discrepancy in modular arithmetic progressions, Super-polynomial accuracy of one dimensional randomized nets using the median of means, Cyclic shifts of the van der Corput set, Entropy, Randomization, Derandomization, and Discrepancy, Point sets with optimal order of extreme and periodic discrepancy, Uniformity of Point Samples in Metric Spaces Using Gap Ratio, A note on stabbing convex bodies with points, lines, and flats, The Phase Transition of Discrepancy in Random Hypergraphs, Oriented discrepancy of Hamilton cycles, STOLARSKY'S INVARIANCE PRINCIPLE FOR FINITE METRIC SPACES, The curse of dimensionality for the $L_p$-discrepancy with finite $p$, Discrepancy of Sums of two Arithmetic Progressions, Discrepancy of arithmetic progressions in grids, On the expected $\mathcal{L}_2$-discrepancy of jittered sampling, Differentially private range query on shortest paths, One-Sided Epsilon-Approximants, Constructive Discrepancy Minimization for Convex Sets, Discrepancy of Digital Sequences: New Results on a Classical QMC Topic, Unnamed Item, Finding exact formulas for the $L_2$ discrepancy of digital $(0,n,2)$-nets via Haar functions, Ordered Ramsey numbers, Connect the dots: how many random points can a regular curve pass through?, Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays, On the Computational Complexity of Linear Discrepancy, Consistent digital rays, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, On the fixed volume discrepancy of the Korobov point sets, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, Transformations and Hardy--Krause Variation, On the exponent of discrepancies, Unnamed Item, Vector balancing games with aging, Comparison of Point Sets and Sequences for Quasi-Monte Carlo and for Random Number Generation, Unnamed Item, Unnamed Item, Unnamed Item, $L_p$- and $S_{p, q}^r B$-discrepancy of the symmetrized van der Corput sequence and modified Hammersley point sets in arbitrary bases, Disjoint edges in complete topological graphs, Towards uniform online spherical tessellations, Better Bin Packing Approximations via Discrepancy Theory, The Communication Complexity of Distributed epsilon-Approximations, Discrepancy of high-dimensional permutations, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, The Khinchin inequality and Chen’s theorem, Point sets with low L p-discrepancy, Unnamed Item, Unnamed Item, Discrepancy of Sums of Arithmetic Progressions, Discrepancy Theory and Quasi-Monte Carlo Integration, Numerical integration and discrepancy under smoothness assumption and without it, On the discrepancy of circular sequences of reals, Geometric systems of unbiased representatives, Optimal approximations made easy, Typical rounding problems, Positive definiteness and the Stolarsky invariance principle, Two dimensional range minimum queries and Fibonacci lattices, $I$-binomial scrambling of digital nets and sequences, A semi-algebraic version of Zarankiewicz's problem, On the root mean square weighted $L_{2}$ discrepancy of scrambled nets, On ordered Ramsey numbers of bounded-degree graphs, Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions, Universal discretization, The test suite generation problem: optimal instances and their implications, Discrepancy bounds for infinite-dimensional order two digital sequences over $\mathbb F_2$, On the mean square weighted $\mathcal {L}_2$ discrepancy of randomized digital nets in prime base, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, Powers of Hamilton cycles of high discrepancy are unavoidable, Scrambled geometric net integration over general product spaces, BMO and exponential Orlicz space estimates of the discrepancy function in arbitrary dimension, The $\varepsilon$-$t$-net problem, Matrix approximation and Tusnády's problem, Spectrally optimized pointset configurations, Connections between numerical integration, discrepancy, dispersion, and universal discretization, On low discrepancy sequences and low discrepancy ergodic transformations of the multidimensional unit cube, Discrepancies of spanning trees and Hamilton cycles, Optimal $L_{p}$-discrepancy bounds for second order digital sequences, Bisecting and $D$-secting families for set systems, The Stolarsky principle and energy optimization on the sphere, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, Geometric characterization of Weyl's discrepancy norm in terms of its $n$-dimensional unit balls, A Koksma-Hlawka inequality for general discrepancy systems, A note on minimal dispersion of point sets in the unit cube, Computer-aided proof of Erdős discrepancy properties, Hardness of discrepancy computation and $\varepsilon$-net verification in high dimension, Asymptotically optimal declustering schemes for 2-dim range queries., From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules, Cubature formulas, discrepancy, and nonlinear approximation, Some open problems concerning the star-discrepancy, The nonzero gain coefficients of Sobol's sequences are always powers of two, On lower bounds for the $L_2$-discrepancy, Relative $(p,\varepsilon )$-approximations in geometry, The BMO-discrepancy suffers from the curse of dimensionality, Optimal periodic $L_2$-discrepancy and diaphony bounds for higher order digital sequences, On the largest empty axis-parallel box amidst $n$ points, Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands, Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension, Tractability properties of the weighted star discrepancy of the Halton sequence, The Kadison-Singer problem in discrepancy theory., Discrepancy estimates for index-transformed uniformly distributed sequences, A metrical lower bound on the star discrepancy of digital sequences, Minimum-link paths revisited, Fibonacci sets and symmetrization in discrepancy theory, Intersections of hypergraphs, An enumerative formula for the spherical cap discrepancy, Optimization-based design of plant-friendly multisine signals using geometric discrepancy criteria, Minimizing interference of a wireless ad-hoc network in a plane, Lower bounds for the number of hyperplanes separating two finite sets of points, Quantum lower bounds by entropy numbers, On the number of maximum empty boxes amidst $n$ points, On some dynamical aspects of NIP theories, Discrepancy of line segments for general lattice checkerboards, New results on the coarseness of bicolored point sets, On the fixed volume discrepancy of the Fibonacci sets in the integral norms, An exact formula for the $L_2$ 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, $\varepsilon$-Mnets: Hitting geometric set systems with subsets, Edge colouring by total labellings, Discrepancy norm: approximation and variations, Lower bounds for weak epsilon-nets and stair-convexity, Discrepancy, chaining and subgaussian processes, Quasi-Monte Carlo methods with applications in finance, The randomized complexity of indefinite integration, Non-independent randomized rounding and coloring, Silver mean conjectures for 15-dimensional volumes and 14-dimensional hyperareas of the separable two-qubit systems, Extremal distributions of discrepancy functions, A nonlocal functional promoting low-discrepancy point sets, Approximating a planar convex set using a sparse grid, Improved bounds and schemes for the declustering problem, Control variates for quasi-Monte Carlo (with comments and rejoinder), Discrepancy of stratified samples from partitions of the unit cube, Rainbow polygons for colored point sets in the plane, Online uniformly inserting points on the sphere, Discrepancy of (centered) arithmetic progressions in ${\mathbb{Z}_p}$, Two proofs for shallow packings, Bounds for discrepancies in the Hamming space, The Geometry of Differential Privacy: The Small Database and Approximate Cases, Distributed noise-shaping quantization. I: Beta duals of finite frames and near-optimal quantization of random measurements, Smooth fixed volume discrepancy, dispersion, and related problems, The VC-dimension of axis-parallel boxes on the torus, When are epsilon-nets small?, Finding optimal volume subintervals with $ k$ points and calculating the star discrepancy are NP-hard problems, Gaussian discrepancy: a probabilistic relaxation of vector balancing, Constructions of $(t,m,s)$-nets and $(t,s)$-sequences, Compositional falsification of cyber-physical systems with machine learning components, On small $n$-uniform hypergraphs with positive discrepancy, Bounds and constructions for the star-discrepancy via $\delta$-covers, On the necessity of low-effective dimension, The chromatic discrepancy of graphs