de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

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

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Doerr, B., Gnewuch, M., & Srivastav, A. (2005). Bounds and Constructions for the Star-Discrepancy via Delta-Covers. Journal of Complexity, 21, 691-709.

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.