Optimal, Suboptimal, and Robust Algorithms for Proximity Graphs