Construction of Minimal Bracketing Covers for Rectangles - Gnewuch, Michael (The Electronic Journal of Combinatorics, 2008)
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 24 (2008) 154-172] 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 δ.