5.2.4 Low-Discrepancy Sampling

In some applications, selecting points that align with the coordinate axis may be undesirable. Therefore, extensive sampling theory has been developed to determine methods that avoid alignments while distributing the points uniformly. In sampling-based motion planning, grids sometimes yield unexpected behavior because a row of points may align nicely with a corridor in ${\cal C}_{free}$. In some cases, a solution is obtained with surprisingly few samples, and in others, too many samples are necessary. These alignment problems, when they exist, generally drive the variance higher in computation times because it is difficult to predict when they will help or hurt. This provides motivation for developing sampling techniques that try to reduce this sensitivity.

Discrepancy theory and its corresponding sampling methods were developed to avoid these problems for numerical integration [738]. Let $X$ be a measure space, such as $[0,1]^n$. Let ${\mathcal R}$ be a collection of subsets of $X$ that is called a range space. In most cases, ${\mathcal R}$ is chosen as the set of all axis-aligned rectangular subsets; hence, this will be assumed from this point onward. With respect to a particular point set, $P$, and range space, ${\mathcal R}$, the discrepancy [965] for $k$ samples is defined as (see Figure 5.7)

$$D(P,{\mathcal R}) = \sup_{R \in {\mathcal R}} \left\{ \left\vert {\vert P \cap R\vert \over k} - {\mu(R) \over \mu(X)} \right\vert \right\} ,$$ (5.22)

in which $\vert P \cap R\vert$ denotes the number of points in $P \cap R$. Each term in the supremum considers how well $P$ can be used to estimate the volume of $R$. For example, if $\mu(R)$ is $1/5$, then we would hope that about $1/5$ of the points in $P$ fall into $R$. The discrepancy measures the largest volume estimation error that can be obtained over all sets in ${\mathcal R}$.

Figure 5.7: Discrepancy measures whether the right number of points fall into boxes. It is related to the chi-square test but optimizes over all possible boxes.