  The complexity of nearest-neighbor search dominates the asymptotic running
time of many sampling-based motion-planning algorithms. However, collision
detection is often considered to be the computational bottleneck in practice.
Examining various asymptotically optimal planning algorithms, we characterize
settings, which we call NN-sensitive, in which the practical computational role
of nearest-neighbor search is far from being negligible, i.e., the portion of
running time taken up by nearest-neighbor search is comparable, or sometimes
even greater than the portion of time taken up by collision detection. This
reinforces and substantiates the claim that motion-planning algorithms could
significantly benefit from efficient and possibly specifically-tailored
nearest-neighbor data structures. The asymptotic (near) optimality of these
algorithms relies on a prescribed connection radius, defining a ball around a
configuration $q$, such that $q$ needs to be connected to all other
configurations in that ball. To facilitate our study, we show how to adapt this
radius to non-Euclidean spaces, which are prevalent in motion planning. This
technical result is of independent interest, as it enables to compare the
radial-connection approach with the common alternative, namely, connecting each
configuration to its $k$ nearest neighbors ($k$-NN). Indeed, as we demonstrate,
there are scenarios where using the radial connection scheme, a solution path
of a specific cost is produced ten-fold (and more) faster than with $k$-NN.
