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

**Nearest K:**The closest points to are considered. This requires setting the parameter (a typical value is ). If you are unsure which implementation to use, try this one.**Component K:**Try to obtain up to nearest samples from each connected component of . A reasonable value is ; otherwise, too many connections would be tried.**Radius:**Take all points within a ball of radius centered at . An upper limit, , may be set to prevent too many connections from being attempted. Typically, . 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 . Note that if the samples are highly regular (e.g., a grid), then choosing the nearest 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 seems preferable.**Visibility:**In Section 5.6.2, a variant will be described for which it is worthwhile to try connecting to all vertices in .

Steven M LaValle 2012-04-20