Bounds and constructions for the star-discrepancy via δ-covers

AbstractFor numerical integration in higher dimensions, bounds for the star-discrepancy with polynomial dependence on the dimension d are desirable. Furthermore, it is still a great challenge to give construction methods for low-discrepancy point sets.In this paper, we give upper bounds for the star-discrepancy and its inverse for subsets of the d-dimensional unit cube. They improve known results. In particular, we determine the usually only implicitly given constants. The bounds are based on the construction of nearly optimal δ-covers of anchored boxes in the d-dimensional unit cube.We give an explicit construction of low-discrepancy points with a derandomized algorithm. The running time of the algorithm, which is exponentially in d, is discussed in detail and comparisons with other methods are given