Computing Bounds for the Star Discrepancy

We observe that the time required to compute the star discrepancy of a sequence of points in a multidimensional unit cube is prohibitive and that the best known upper bounds for the star discrepancy of (t,s)-sequences and (t,m,s)-nets are useful only for sample sizes that grow exponentially with the dimension s. Then, an algorithm to compute upper bounds for the star discrepancy of an arbitrary set of n points in the s-dimensional unit cube is proposed. For an integer k≥1, this algorithm computes in O(nslogk+2^s*k^s) time and O(k^s) space a bound that is no better than a function depending on s and k. As an application, we give improved upper bounds for the star discrepancy of some Faure (0,m,s)-nets for s∈{7,…,20}.


Published in:
Computing, 65, 2, 169-186
Year:
2000
Keywords:
Note:
PRO 2000.09
Other identifiers:
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)