Selecting neighboring samples

Several possible implementations of line 5 can be made. In all of these, it seems best to sort the vertices that will be considered for connection in order of increasing distance from ${\alpha }(i)$. This makes sense because shorter paths are usually less costly to check for collision, and they also have a higher likelihood of being collision-free. If a connection is made, this avoids costly collision checking of longer paths to configurations that would eventually belong to the same connected component.

Several useful implementations of NEIGHBORHOOD are

1. Nearest K: The $K$ closest points to ${\alpha }(i)$ are considered. This requires setting the parameter $K$ (a typical value is $15$). If you are unsure which implementation to use, try this one.
2. Component K: Try to obtain up to $K$ nearest samples from each connected component of ${\cal G}$. A reasonable value is $K=1$; otherwise, too many connections would be tried.
3. Radius: Take all points within a ball of radius $r$ centered at ${\alpha }(i)$. An upper limit, $K$, may be set to prevent too many connections from being attempted. Typically, $K = 20$. A radius can be determined adaptively by shrinking the ball as the number of points increases. This reduction can be based on dispersion or discrepancy, if either of these is available for ${\alpha }$. Note that if the samples are highly regular (e.g., a grid), then choosing the nearest $K$ and taking points within a ball become essentially equivalent. If the point set is highly irregular, as in the case of random samples, then taking the nearest $K$ seems preferable.
4. Visibility: In Section 5.6.2, a variant will be described for which it is worthwhile to try connecting ${\alpha }$ to all vertices in ${\cal G}$.

Note that all of these require ${\cal C}$ to be a metric space. One variation that has not yet been given much attention is to ensure that the directions of the NEIGHBORHOOD points relative to ${\alpha }(i)$ are distributed uniformly. For example, if the $20$ closest points are all clumped together in the same direction, then it may be preferable to try connecting to a further point because it is in the opposite direction.