Computing bounds for the star discrepancy
From MaRDI portal
The author presents on algorithm to compute upper bounds for the star discrepancy of an arbitrary set of \(n\) points in the \(s\)-dimensional unit cube. For an integer \(k\geq 1\), this algorithm computes in \({\mathcal O}(ns\log k+2^s k^2)\) time and \({\mathcal O}(k^s)\) space a bound that is no better than a function depending on \(k\) and \(s\). As an application, new upper bounds for the star discrepancy of some Faure \((0,m,s)\)-nets for \(s\in\{7, \dots, 20\}\) are given.
Recommendations
- An algorithm to compute bounds for the star discrepancy
- An intermediate bound on the star discrepancy
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- On an explicit lower bound for the star discrepancy in three dimensions
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- An elementary proof of a lower bound for the inverse of the star discrepancy
- A random walk algorithm to estimate a lower bound of the star discrepancy
- Tractability results for the weighted star-discrepancy
- Some open problems concerning the star-discrepancy
- An improved bound for the star discrepancy of sequences in the unit interval
Cited in
(15)- Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
- An algorithm to compute bounds for the star discrepancy
- Tractability properties of the weighted star discrepancy of regular grids
- Star discrepancy subset selection: problem formulation and efficient approaches for low dimensions
- Bounds and constructions for the star-discrepancy via \(\delta\)-covers
- A genetic algorithm approach to estimate lower bounds of the star discrepancy
- A best possible upper bound on the star discrepancy of (t, m, 2)-nets
- Statistical measures of two dimensional point set uniformity
- Calculation of discrepancy measures and applications
- Entropy, Randomization, Derandomization, and Discrepancy
- An intermediate bound on the star discrepancy
- A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
- Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
- On the discrepancy of low-dimensional probability measures
- Calculation of the discrepancy of a finite set of points in the unit n -cube
This page was built for publication: Computing bounds for the star discrepancy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1592539)
