There are many different asymptotic bounds for discrepancy, depending on the particular range space and measure space [682]. The most widely referenced bounds are based on the standard range space of axis-aligned rectangular boxes in . There are two different bounds, depending on whether the number of points, , is given. The best possible asymptotic discrepancy for a single sequence is . This implies that is not specified. If, however, for every a new set of points can be chosen, then the best possible discrepancy is . This bound is lower because it considers the best that can be achieved by a sequence of points sets, in which every point set may be completely different. In a single sequence, the next set must be extended from the current set by adding a single sample.

Steven M LaValle 2012-04-20