Asymptotic bounds

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 $ [0,1]^n$. There are two different bounds, depending on whether the number of points, $ k$, is given. The best possible asymptotic discrepancy for a single sequence is $ O(k^{-1}\log^n k)$. This implies that $ k$ is not specified. If, however, for every $ k$ a new set of points can be chosen, then the best possible discrepancy is $ O(k^{-1}\log^{n-1} k)$. 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