An algorithm to compute bounds for the star discrepancy

Abstract: We propose an algorithm to compute upper and lower bounds for the star discrepancy of an arbitrary sequence of points in the s-dimensional unit cube. The method is based on a particular partition of the unit cube into subintervals and on a specialized procedure for orthogonal range counting. The cardinality of the partition depends on the dimension and on an accuracy parameter that has to be specified. We have implemented this method and here we present results of some computational experiments obtained with this implementation.

The algorithm proposed in this paper has been implemented in C. Two versions are available:

• The full version (as described in the paper, it uses range trees for counting)
• The simplified version (it doesn't use range trees, runs much slower but requires less memory than the full version)

Two file formats are possible to give the point set x={x₁,...,x_n} in I^s=[0,1)^s:

• As real numbers: x_i=(x_i,1,...,x_i,s)
  The file must contain the n+1 following lines:
  
  
  s n reals
  x_1,1 x_1,2 ... x_1,s
  ...
  x_n,1 x_n,2 ... x_n,s



Example: x={(0,0),(0.5,0.5),(0.75,0.25),(0.25,0.75)}

• As fractions: x_i,j=num_i,j / den_i
  The file must contain the n+1 following lines:
  
  
  s n fractions
  num_1,1 num_1,2 ... num_1,s den₁
  ...
  num_n,1 num_n,2 ... num_n,s den_n

Example: x={(0,0),(1/2,1/2),(3/4,1/4),(1/4,3/4)}

Last update: June 15, 2000