Dispersion definition

The dispersion5.6of a finite set $ P$ of samples in a metric space $ (X,\rho)$ is5.7

$\displaystyle \delta(P) = \sup_{x \in X} \big\{ \min_{p \in P} \big\{ \rho(x,p) \big\}\big\}.$ (5.19)

Figure 5.4 gives an interpretation of the definition for two different metrics. An alternative way to consider dispersion is as the radius of the largest empty ball (for the $ L_\infty$ metric, the balls are actually cubes). Note that at the boundary of $ X$ (if it exists), the empty ball becomes truncated because it cannot exceed the boundary. There is also a nice interpretation in terms of Voronoi diagrams. Figure 5.3 can be used to help explain $ L_2$ dispersion in $ {\mathbb{R}}^2$. The Voronoi vertices are the points at which three or more Voronoi regions meet. These are points in $ {\cal C}$ for which the nearest sample is far. An open, empty disc can be placed at any Voronoi vertex, with a radius equal to the distance to the three (or more) closest samples. The radius of the largest disc among those placed at all Voronoi vertices is the dispersion. This interpretation also extends nicely to higher dimensions.

Steven M LaValle 2012-04-20