Find all nearby points in a set, for each element of the set Given a finite set $S$ of points in $\mathbb R^p$ and a number $\rho$, my collaborators and I want to find, for each $s\in S$, the other points in $S$ that are within $\rho$ of $s$. Of course there's the obvious $O(|S|^2)$ algorithm, and we also came up with something (roughly, sort in each dimensions, then for each dimension and for each element of $S$ mark nearby points in some sparse matrices, and then combine the sparse matrices) that has better running time under certain assumptions, but not in the worst case.

I feel that this must be a standard problem, but I haven't been able to find references. I was wondering if someone here knows what I should search for or can suggest a good reference to start from?

Thanks in advance!
I think what you are looking for is the Fixed-radius near neighbors problem.