On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

This research paper investigates the fundamental limitations of sampling-based methods for reachability analysis in robotics and safety-critical control. The authors identify specific geometric and dynamic regularity properties required to achieve accurate reachable-set recovery and derive a sample complexity bound that scales exponentially with state dimension and time horizon. Through minimax lower bounds, they demonstrate that this exponential dependence is intrinsic to the problem class, not an artifact of existing algorithms. Experiments on nonlinear systems further confirm that while adversarial sampling can improve constant factors, it cannot alter the fundamental scaling behavior.