Thus, it is important to realize that even the ``random'' samples are
deterministic. They are designed to optimize performance on
statistical tests. Many sophisticated statistical tests of uniform
randomness are used. One of the simplest, the *chi-square test*,
is described here. This test measures how far computed statistics are
from their expected value. As a simple example, suppose
and is partitioned into a by array of square
boxes. If a set of samples is chosen at random, then
intuitively each box should receive roughly of the samples.
An error function can be defined to measure how far from true this
intuition is:

(5.18) |

in which is the number of samples that fall into box . It is shown [521] that follows a

This irregularity can be observed in terms of *Voronoi
diagrams*, as shown in Figure
5.3. The Voronoi diagram partitions
into
regions based on the samples. Each sample has an associated
*Voronoi region*
. For any point
, is
the closest sample to using Euclidean distance. The different
sizes and shapes of these regions give some indication of the
required irregularity of random sampling. This irregularity may be
undesirable for sampling-based motion planning and is somewhat
repaired by the deterministic sampling methods of Sections
5.2.3 and 5.2.4 (however, these methods also
have drawbacks).

Steven M LaValle 2012-04-20