Infinite grid sequences

Now suppose that the number, $k$, of samples is not given. The task is to define an infinite sequence that has the nice properties of the van der Corput sequence but works for any dimension. This will become the notion of a multi-resolution grid. The resolution can be iteratively doubled. For a multi-resolution standard grid in ${\mathbb{R}}^n$, the sequence will first place one point at the origin. After $2^n$ points have been placed, there will be a grid with two points per axis. After $4^n$ points, there will be four points per axis. Thus, after $2^{ni}$ points for any positive integer $i$, a grid with $2^i$ points per axis will be represented. If only complete grids are allowed, then it becomes clear why they appear inappropriate for high-dimensional problems. For example, if $n = 10$, then full grids appear after $1$, $2^{10}$, $2^{20}$, $2^{30}$, and so on, samples. Each doubling in resolution multiplies the number of points by $2^n$. Thus, to use grids in high dimensions, one must be willing to accept partial grids and define an infinite sequence that places points in a nice way.

The van der Corput sequence can be extended in a straightforward way as follows. Suppose $X = {\mathbb{T}}^2 = [0,1]^2{/\sim}$. The original van der Corput sequence started by counting in binary. The least significant bit was used to select which half of $[0,1]$ was sampled. In the current setting, the two least significant bits can be used to select the quadrant of $[0,1]^2$. The next two bits can be used to select the quadrant within the quadrant. This procedure continues recursively to obtain a complete grid after $k = 2^{2i}$ points, for any positive integer $i$. For any $k$, however, there is only a partial grid. The points are distributed with optimal $L_\infty$ dispersion. This same idea can be applied in dimension $n$ by using $n$ bits at a time from the binary sequence to select the orthant ($n$-dimensional quadrant). Many other orderings produce $L_\infty$-optimal dispersion. Selecting orderings that additionally optimize other criteria, such as discrepancy or $L_2$ dispersion, are covered in [639,644]. Unfortunately, it is more difficult to make a multi-resolution Sukharev grid. The base becomes $3$ instead of $2$; after every $3^{ni}$ points a complete grid is obtained. For example, in one dimension, the first point appears at $1/2$. The next two points appear at $1/6$ and $5/6$. The next complete one-dimensional grid appears after there are $9$ points.