The fixed-radius near neighbor is a *O(n + k)* algorithm, where *k* is the number of pairs to get reported.
Note that if *k < n ^{2}* then this algorithm should perform better than the naive

Further Reading:

- "The complexity of finding fixed-radius near neighbors" by JL Bentley, DF Stanat, and EH Williams
- Lecture 1 of Computational Geometry by D Mount for the proof of the runtime and a more intuitive read