Robust Proximity Queries: An Illustration of Degree-driven Algorithms Design