Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916400314974208 |
|---|---|
| author | Gnewuch, Michael |
| author_facet | Gnewuch, Michael |
| contents | We improve the best known upper bound for the bracketing number of $d$-dimensional axis-parallel boxes anchored in $0$ (or, put differently, of lower left orthants intersected with the $d$-dimensional unit cube $[0,1]^d$). More precisely, we provide a better upper bound for the cardinality of an algorithmic bracketing cover construction due to Eric Thiémard, which forms the core of his algorithm to approximate the star discrepancy of arbitrary point sets from [E. Thiémard, An algorithm to compute bounds for the star discrepancy, J.~Complexity 17 (2001), 850 -- 880].
Moreover, the new upper bound for the bracketing number of anchored axis-parallel boxes yields an improved upper bound for the bracketing number of arbitrary axis-parallel boxes in $[0,1]^d$.
In our upper bounds all constants are fully explicit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00801 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy Gnewuch, Michael Combinatorics Computational Geometry Discrete Mathematics We improve the best known upper bound for the bracketing number of $d$-dimensional axis-parallel boxes anchored in $0$ (or, put differently, of lower left orthants intersected with the $d$-dimensional unit cube $[0,1]^d$). More precisely, we provide a better upper bound for the cardinality of an algorithmic bracketing cover construction due to Eric Thiémard, which forms the core of his algorithm to approximate the star discrepancy of arbitrary point sets from [E. Thiémard, An algorithm to compute bounds for the star discrepancy, J.~Complexity 17 (2001), 850 -- 880]. Moreover, the new upper bound for the bracketing number of anchored axis-parallel boxes yields an improved upper bound for the bracketing number of arbitrary axis-parallel boxes in $[0,1]^d$. In our upper bounds all constants are fully explicit. |
| title | Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy |
| topic | Combinatorics Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2401.00801 |