Benjamin Doerr, Michael Gnewuch, Anand Srivastav:

Bounds and Construction for the Star-Discrepancy via Delta-Covers

For 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. We also show an explicit construction with a derandomized algorithm. This resolves two open problems posed by Heinrich [J. Complexity 19 (2003) 416-419].

Our results are based on the construction of nearly optimal Delta-covers of anchored boxes in the d-dimensional unit cube.

Mathematics Subject Classification (1991): 11K38

Bibliographical note: Journal of Complexity, Vol. 21(5), pp. 691-709, October 2005

Keywords: Covering number, derandomization, low-discrepancy point sets, probabilistic methods, star-discrepancy

Mail an Jens Burmeister

[Thu Feb 19 18:56:36 2009]

Impressum