Deterministic constructions of high-dimensional sets with small dispersion

Abstract

The dispersion of a point set $P\subset [0,1{]}^d$ is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect $P$. Here, we show a construction of low-dispersion point sets, which can be deduced from solutions of certain $k$-restriction problems, which are well-known in coding theory. It was observed only recently that, for any $\epsilon >0$, certain randomized constructions provide point sets with dispersion smaller than $\epsilon$ and number of elements growing only logarithmically in $d$. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial in $d$. Note that, however, the running-time will be super-exponential in ${\epsilon }^{-1}$.