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

Hilfe Wegweiser Impressum Kontakt Einloggen

# 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.