07-14   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Michael Gnewuch:

Construction of Minimal Bracketing Covers for Rectangles

We construct explicit δ-bracketing covers with minimal cardinality for the set system of (anchored) rectangles in the two dimensional unit cube. More precisely, the cardinality of these δ-bracketing covers are bounded from above by δ-2 + o(δ-2). A lower bound for the cardinality of arbitrary δ-bracketing covers for d-dimensional anchored boxes from [M. Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 2007] implies the lower bound δ-2+O(δ-1) in dimension d=2, showing that our constructed covers are (essentially) optimal.

We study also other δ-bracketing covers for the set system of rectangles, deduce the coefficient of the most significant term δ-2 in the asymptotic expansion of their cardinality, and compute their cardinality for explicit values of δ.

Mathematics Subject Classification (1991): 60C05, 11K38

Bibliographical note: The Electronic Journal of Combinatorics 15(1), Research Paper 95, 2008.

Keywords: bracketing cover, bracketing number, metric entropy, uniform distribution, star discrepancy, extreme discrepancy

Mail an Jens Burmeister
[Thu Feb 19 18:56:37 2009]
Impressum