How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this? Suppose that I have a set of $N$ points in $k$-dimensional space ($k&gt;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.
There's an enormous amount of work on data structures and algorithms for this sort of problem.  I suggest you start by reading the general literature on this problem.

Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem.  Those techniques are applicable to your problem.

Then, read about quadtrees, octrees, k-d trees, VP trees, and the general category of BSP trees.