New bounds on the minimal dispersion (Q2145076)

Given a finite subset \(P\) of the unit cube \([0,1]^d\), its \emph{dispersion} is the supremum over the volumes of all axis parallel boxes that are disjoint to \(P\) and contained in \([0,1)^d\). According to [\textit{G. Rote} and \textit{R. F. Tichy}, Math. Comput. Modelling 23, No. 8-9, 9--23 (1996; Zbl 0855.11041)], the \textit{minimal dispersion} is defined as the function in two variables sending \((n,d)\) to the infimum of all dispersions that arise in the above manner from sets \(P\) of cardinality \(n\) contained in \([0,1]^d\). A main theme of the paper is to improve known upper bounds for this minimal dispersion and its inverse function in both the periodic and non-periodic settings. To this end a new construction for a set of boxes approximating axis-parallel boxes of fixed volume in \([0, 1]^d\) is given. In the case of random choice of points, the newly established bounds turn out to be sharp up to a double logarithmic factor. Further applications deal with the more general notion of \(k\)-\textit{dispersion}, where -- loosely speaking -- the axis-parallel boxes from the above are allowed to intersect \(P\) in at most \(k\) points.