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 D_n^* and defined as

D_n^* = supremum ( P in I* ) | ( A(P,x) / n ) - lambda ( P ) |

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

• epsilon is an error tolerance between 0 and 1, and indicates the allowable error in the estimate;
• n is the number of points to be read from the file;
• table_file is a file in table format containing at least n points. The dimensionality of the pointset is inferred from the file.

star_discrepancy epsilon n table_file num den

where the two extra arguments are:

• num the optional balance numerator;
• den the optional balance denominator;

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:

• star_discrepancy.cpp, the source code.

Examples and Tests:

• halton_02_00010.txt, 10 Halton points in 2D.
• halton_02_00010_output.txt, the result of the command

  star_discrepancy 0.001 10 halton_02_00010.txt

List of Routines:

• MAIN is the main program for the star discrepancy bound computation.
• CH_EQI is true if two characters are equal, disregarding case.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DATA_READ reads coordinate data from a file.
• DECOMPOSITION carries out the decomposition of a subinterval.
• EXPLORE ???
• FASTEXPLORE ???
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_ROW_COUNT counts the number of row records in a file.
• FILE_USAGE lists the legal input file format.
• FREETREE frees storage associated with a tree.
• INITLEX ???
• INITPARAMETERS sets program parameters based on user input and defaults.
• INSERTLEX ???
• LOWBOUND ???
• MEMORY prints a message and terminates on memory allocation errors.
• QUICKSORT uses Quicksort to sort an array.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• SUBTREE ???
• SUPERTREE ???
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRAITER ???
• USAGE prints usage information for the program.

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