The van der Corput sequence

A beautiful yet underutilized sequence was published in 1935 by van der Corput, a Dutch mathematician [952]. It exhibits many ideal qualities for applications. At the same time, it is based on a simple idea. Unfortunately, it is only defined for the unit interval. The quest to extend many of its qualities to higher dimensional spaces motivates the formal quality measures and sampling techniques in the remainder of this section.

To explain the van der Corput sequence, let ${\cal C}= [0,1] {/\sim}$, in which $0 \sim 1$, which can be interpreted as $SO(2)$. Suppose that we want to place $16$ samples in ${\cal C}$. An ideal choice is the set $S = \{i/16 \;\vert\; 0 \leq i < 16 \}$, which evenly spaces the points at intervals of length $1/16$. This means that no point in ${\cal C}$ is further than $1/32$ from the nearest sample. What if we want to make $S$ into a sequence? What is the best ordering? What if we are not even sure that $16$ points are sufficient? Maybe $16$ is too few or even too many.

Figure 5.2: The van der Corput sequence is obtained by reversing the bits in the binary decimal representation of the naive sequence.

The first two columns of Figure 5.2 show a naive attempt at making $S$ into a sequence by sorting the points by increasing value. The problem is that after $i = 8$, half of ${\cal C}$ has been neglected. It would be preferable to have a nice covering of ${\cal C}$ for any $i$. Van der Corput's clever idea was to reverse the order of the bits, when the sequence is represented with binary decimals. In the original sequence, the most significant bit toggles only once, whereas the least significant bit toggles in every step. By reversing the bits, the most significant bit toggles in every step, which means that the sequence alternates between the lower and upper halves of ${\cal C}$. The third and fourth columns of Figure 5.2 show the original and reversed-order binary representations. The resulting sequence dances around $[0,1]{/\sim}$ in a nice way, as shown in the last two columns of Figure 5.2. Let ${\nu}(i)$ denote the $i$th point of the van der Corput sequence.

In contrast to the naive sequence, each ${\nu}(i)$ lies far away from ${\nu}(i+1)$. Furthermore, the first $i$ points of the sequence, for any $i$, provide reasonably uniform coverage of ${\cal C}$. When $i$ is a power of $2$, the points are perfectly spaced. For other $i$, the coverage is still good in the sense that the number of points that appear in any interval of length $l$ is roughly $i l$. For example, when $i= 10$, every interval of length $1/2$ contains roughly $5$ points.

The length, $16$, of the naive sequence is actually not important. If instead $8$ is used, the same ${\nu}(1)$, $\ldots$, ${\nu}(8)$ are obtained. Observe in the reverse binary column of Figure 5.2 that this amounts to removing the last zero from each binary decimal representation, which does not alter their values. If $32$ is used for the naive sequence, then the same ${\nu}(1)$, $\ldots$, ${\nu}(16)$ are obtained, and the sequence continues nicely from ${\nu}(17)$ to ${\nu}(32)$. To obtain the van der Corput sequence from ${\nu}(33)$ to ${\nu}(64)$, six-bit sequences are reversed (corresponding to the case in which the naive sequence has $64$ points). The process repeats to produce an infinite sequence that does not require a fixed number of points to be specified a priori. In addition to the nice uniformity properties for every $i$, the infinite van der Corput sequence is also dense in $[0,1]{/\sim}$. This implies that every open subset must contain at least one sample.

You have now seen ways to generate nice samples in a unit interval both randomly and deterministically. Sections 5.2.2-5.2.4 explain how to generate dense samples with nice properties in the complicated spaces that arise in motion planning.