Construction of minimal bracketing covers for rectangles

zbMATH Open1165.05317arXiv0807.4446MaRDI QIDQ1010822FDOQ1010822

Authors: Michael Gnewuch 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We construct explicit $delta$-bracketing covers with minimal cardinality for the set system of (anchored) rectangles in the two dimensional unit cube. More precisely, the cardinality of these $delta$-bracketing covers are bounded from above by $delt{a}^{-2}+o(delt{a}^{-2})$. A lower bound for the cardinality of arbitrary $delta$-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 $delt{a}^{-2}+O(delt{a}^{-1})$ in dimension $d=2$, showing that our constructed covers are (essentially) optimal. We study also other $delta$-bracketing covers for the set system of rectangles, deduce the coefficient of the most significant term $delt{a}^{-2}$ in the asymptotic expansion of their cardinality, and compute their cardinality for explicit values of $delta$.

Full work available at URL: https://arxiv.org/abs/0807.4446

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Covering boxes by points
• Covering the \(d\)-dimensional unit cube by \(n\) rectangular boxes of smaller diameter
• An upper bound of the minimal dispersion via delta covers
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy

zbMATH Keywords

anchored boxesbracketing covers

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Combinatorial aspects of packing and covering (05B40) Combinatorial complexity of geometric structures (52C45)

Cited In (10)

• Probabilistic star discrepancy bounds for double infinite random matrices
• On probabilistic results for the discrepancy of a hybrid-Monte Carlo sequence
• Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
• Covering numbers, dyadic chaining and discrepancy
• Probabilistic discrepancy bound for Monte Carlo point sets
• Title not available (Why is that?)
• Calculation of discrepancy measures and applications
• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• Entropy, Randomization, Derandomization, and Discrepancy
• Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy

This page was built for publication: Construction of minimal bracketing covers for rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010822)