Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$. The brute-force method would require $N(N-1)$ distance calculations, which is not acceptable. I attack the problem by first sorting the cells in a grid¹, such as in this answer, followed by brute-force within each grid cell and a number of neighbours (which is easily calculated from the cell size $w*h$ and the maximum distance $t$).
My solution seems to work acceptably well for my purposes, and the results appear to be correct. However I'm neither a computer scientist nor a mathematician, and I'm not sure what tools I could use to calculate the optimal cell size. In fact, I developed the aforementioned possibly naive algorithm because it seemed like a reasonably okay method. I guess the optimal cell size depends in some way on $N$, $t$, on the cost of the distance function, and on the implementation of the sorting in cells, on the distribution of points, and on other things. How would I make a guess of the optimal values of $w$ and $h$, with or without a priori knowledge on the approximate number of pairs I expect to find?
Does the answer change if the N points are divided in two sets $S_1$ and $S_2$, and each pair shall consist of one element from each set?
¹Not necessarily euclidian. The points may, for example, be locations on a sphere, i.e. on Earth, with latitude and longitude.