5.2.3 Low-Dispersion Sampling

**Figure 5.4:** Reducing the dispersion means reducing the radius of the largest empty ball.
$\begin{figure}\begin{center} \begin{tabular}{ccc} \psfig{figure=figs/dispersion.... ...dispersion & & (b) $L_\infty$ dispersion \end{tabular}\end{center} \end{figure}$

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.''

Subsections

Steven M LaValle 2012-04-20