Dispersion bounds

Since the sample sequence is infinite, it is interesting to consider asymptotic bounds on dispersion. It is known that for $ X = [0,1]^n$ and any $ L_p$ metric, the best possible asymptotic dispersion is $ O(k^{-1/n})$ for $ k$ points and $ n$ dimensions [738]. In this expression, $ k$ is the variable in the limit and $ n$ is treated as a constant. Therefore, any function of $ n$ may appear as a constant (i.e., $ O(f(n)k^{-1/n}) = O(k^{-1/n})$ for any positive $ f(n)$). An important practical consideration is the size of $ f(n)$ in the asymptotic analysis. For example, for the van der Corput sequence from Section 5.2.1, the dispersion is bounded by $ 1/k$, which means that $ f(n) = 1$. This does not seem good because for values of $ k$ that are powers of two, the dispersion is $ 1/2k$. Using a multi-resolution Sukharev grid, the constant becomes $ 3/2$ because it takes a longer time before a full grid is obtained. Nongrid, low-dispersion infinite sequences exist that have $ f(n) =
1/\ln 4$ [738]; these are not even uniformly distributed, which is rather surprising.

Steven M LaValle 2012-04-20