アイテム詳細

要旨

For numerical integration in higher dimensions, bounds for the star-dis\-cre\-pan\-cy 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$-di\-men\-sio\-nal 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 $\delta$-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.