Construction of minimal bracketing covers for rectangles

MaRDI QIDQ1010822zbMATH OpenFDO

Authors Michael Gnewuch

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0807.4446, https://eudml.org/doc/130278, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r95.html

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

zbMATH Keywords

anchored boxesbracketing covers

Mathematics Subject Classification ID

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

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

Review text

Summary: 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 \(\delta^{-2} + o(\delta^{-2})\). A lower bound for the cardinality of arbitrary \(\delta\)-bracketing covers for \(d\)-dimensional anchored boxes from [\textit{M. Gnewuch}, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J.Complexity 24, No.\,2, 154--172 (2008; Zbl 1138.11031)] implies the lower bound \(\delta^{-2}+O(\delta^{-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 \(\delta^{-2}\) in the asymptotic expansion of their cardinality, and compute their cardinality for explicit values of \(\delta\).

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

Cited in

(10)

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

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)