5.2.3 Low-Dispersion Sampling

Figure 5.4: Reducing the dispersion means reducing the radius of the largest empty ball.
...dispersion & & (b) $L_\infty$ dispersion

This section describes an alternative to random sampling. Here, the goal is to optimize a criterion called dispersion [738]. Intuitively, the idea is to place samples in a way that makes the largest uncovered area be as small as possible. This generalizes of the idea of grid resolution. For a grid, the resolution may be selected by defining the step size for each axis. As the step size is decreased, the resolution increases. If a grid-based motion planning algorithm can increase the resolution arbitrarily, it becomes resolution complete. Using the concepts in this section, it may instead reduce its dispersion arbitrarily to obtain a resolution complete algorithm. Thus, dispersion can be considered as a powerful generalization of the notion of ``resolution.''


Steven M LaValle 2012-04-20