Deterministic Constructions of High-Dimensional Sets with Small Dispersion

The dispersion of a point set P⊂ [0,1]^d is the volume of the largest box with sides parallel to the coordinate axes, which does not intersect P . It was observed only recently that, for any ε >0 , certain randomized constructions provide point sets with dispersion smaller than ε 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 ε ^-1 . Our construction is based on the apparently new insight that low-dispersion point sets can be deduced from solutions of certain k -restriction problems, which are well-known in coding theory.