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

Authors and Affiliations

1. Département de Mathématiques École Polytechnique Fédérale de Lausanne CH-1015 Lausanne, Switzerland e-mail: eric.thiemard@epfl.ch, , , , , , CH

   E. Thiémard

Received April 20, 1999; revised April 26, 2000

Reprints and permissions