An Upper Bound of the Minimal Dispersion via Delta Covers
Provides theoretical guarantees for the minimal dispersion problem, relevant to discrepancy theory and quasi-Monte Carlo methods.
The paper proves an upper bound on the minimal dispersion (largest empty test set volume) for point sets in the unit cube, achieving bounds of O((d/n) log(n/d)) for axis-parallel boxes and O((d/n) log n) on the torus.
For a point set of $n$ elements in the $d$-dimensional unit cube and a class of test sets we are interested in the largest volume of a test set which does not contain any point. For all natural numbers $n$, $d$ and under the assumption of a $delta$-cover with cardinality $\vert Γ_δ\vert$ we prove that there is a point set, such that the largest volume of such a test set without any point is bounded by $\frac{\log \vert Γ_δ\vert}{n} + δ$. For axis-parallel boxes on the unit cube this leads to a volume of at most $\frac{4d}{n}\log(\frac{9n}{d})$ and on the torus to $\frac{4d}{n}\log (2n)$.