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

For numerical integration in higher dimensions, bounds for the star-discre-pancy with polynomial dependence on the dimension d are desirable. Fur-thermore, 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 deran-domized algorithm. The running time of the algorithm, which is exponen-tially in d, is discussed in detail and comparisons with other methods are given