Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
21/2007

Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy

Michael Gnewuch

Abstract

In the first part of this paper we derive lower bounds and constructive upper bounds for the bracketing numbers of anchored and unanchored axis-parallel boxes in the $d$-dimensional unit cube.

In the second part we apply these results to geometric discrepancy. We derive upper bounds for the inverse of the star and the extreme discrepancy with explicitly given small constants and an optimal dependence on the dimension $d$, and provide corresponding bounds for the star and the extreme discrepancy itself. These bounds improve known results from [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for the star-discrepancy via $\delta$-covers. J. Complexity 21 (2005), 691-709], [M. Gnewuch. Bounds for the average $L^p$-extreme and the $L^\infty$-extreme discrepancy, Electron. J. Combin. 12 (2005), Research Paper 54] and [H. N. Mhaskar. On the tractibility of multivariate integration and approximation by neural networks. J. Complexity 20 (2004), 561-590].

We also discuss an algorithm from [E. Thiémard, An algorithm to compute bounds for the star discrepancy, J. Complexity 17 (2001), 850-880] to approximate the star-discrepancy of a given $n$-point set. Our lower bound on the bracketing number of anchored boxes, e.g., leads directly to a lower bound of the running time of Thiémard's algorithm. Furthermore, we show how one can use our results to modify the algorithm to approximate the extreme discrepancy of a given set.

Received:
Feb 26, 2007
Published:
Feb 26, 2007
MSC Codes:
11K38
Keywords:
star discrepancy, extreme discrepancy, bracketing number, covering number, metric entropy

Related publications

inJournal
2008 Repository Open Access
Michael Gnewuch

Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy

In: Journal of complexity, 24 (2008) 2, pp. 154-172