Collision detection or nearest-neighbor search? On the computational bottleneck in sampling-based motion planning

Michal Kleinbort, Oren Salzman, Dan Halperin

The complexity of nearest-neighbor search dominates the asymptotic running time of many sampling-based motion-planning algorithms. However, collision detection is often considered…