STAR_DISCREPANCY
The Star Discrepancy of a Pointset


STAR_DISCREPANCY is a C++ program which computes bounds on the star discrepancy of an M-dimensional set of N points contained in the unit hypercube, by Eric Thiemard.

The pointset is stored in a file, in the TABLE format.

The star discrepancy is a commonly cited statistic for determining how uniformly a pointset is distributed over a region. For convenience, this region is usually taken as the unit hypercube; STAR_DISCREPANCY will assume that datasets under investigation are meant to fill up the unit hypercube.

If the pointset to be investigated actually lies in some other hypercube, a simply translation and rescaling may be enough to transform the data. This will probably NOT be satisfactory if the original region is rectangular, but has sides of different length, or if the region is not rectangular.

The discrepancy measures the worst error that would be made in estimating the area of a subregion of the hypercube by simply noting the fraction of the pointset contained in the subregion. If arbitrary subregions were allowed, then it would always be possible to make this error equal to 1 (just take the region consisting of the hypercube minus the pointset.) Since any "reasonable" area can be arbitrarily well approximated by rectangles, the star discrepancy calculation uses only rectangular subregions, whose sides are aligned with coordinates directions, and one of whose corners is at the origin.

Formally, the star discrepancy of a pointset of n points is symbolized by Dn* and defined as

Dn* = supremum ( P in I* ) | ( A(P,x) / n ) - lambda ( P ) |
Here, I* is the set of all M-dimensional subintervals of the form [0,p1] x [0,p2] x ... x [0,ps] where every p is between 0 and 1; P is any such subinterval; lambda(P) is the volume of the subinterval, A(P,x) is the number of points of the point set x that occur in P, and n is the number of points in x.

Clearly, the star discrepancy is measuring how badly the pointset estimates the volume of a subinterval. This worst error is somewhere between 0 (absolutely no error ever) and 1 (totally missing the volume of the unit hypercube). A value of 0.25, for instance, means that there is a subinterval in the unit hypercube for which the difference between its true and estimated volumes is 0.25. (It might have a volume of 0.80, and be estimated at 0.55, for instance, or a volume of 0.05 that is estimated at 0.30.)

The original program is by Eric Thiemard. Changes have been made to the program so that it compiles under C++, uses a simpler datafile format, and infers the dimensionality of the data from the information in the datafile.

Usage:

star_discrepancy epsilon n table_file
star_discrepancy epsilon n table_file num den
where the two extra arguments are:

Languages:

STAR_DISCREPANCY is available in a C version and a C++ version.

Related Data and Programs:

DIAPHONY, a C++ program which reads a file of N points in M dimensions and computes its diaphony, a measure of point dispersion.

TABLE_LATINIZE, a C++ program which can read a TABLE file and write out a "latinized" version.

TABLE_QUALITY, a C++ program which can read a TABLE file and print out measures of the quality of dispersion of the points.

Author:

Eric Thiemard

Reference:

  1. http://rosowww.epfl.ch/papers/discrbound2/, the source code web site.
  2. Eric Thiemard,
    An Algorithm to Compute Bounds for the Star Discrepancy,
    Journal of Complexity,
    Volume 17, pages 850-880, 2001.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the C++ source codes.


Last revised on 12 November 2006.