Finding pairs closer than a given distance (proximity) in a set of points

You are not looking for clustering algorithms.

Instead, you are looking for a database index that supports radius queries.

Examples:

• R*-tree
• kd-tree
• M-tree
• Gridfile
• Octree (for 3d, quadtree for 2d)

Any of these should do the trick, and yield an O(n log n) performance theoretically. In practise, it's not as easy as this. If all your objects are really close, "closer than a given coordinate" may mean every object, i.e. O(n^2).

What you are looking for is a quadtree in 3 dimensions, i.e. an octree. An octree is basically the same as the binary tree, but instead of two children per node, it has 2^D = 2^3 = 8 children per node, where D is the dimension.

For example, imagine a cube. In order to create the next level of the root, you actually have every node representing the 8 sub-cubes inside the cube and so on.

This tree will yield fast lookups but careful not to use it for more dimensions. I had built a polymorphic quadtree and wouldn't go to more than 8-10 dimensions, because it was becoming too flat.

The other approach would be the kd-tree, where actually you halve the dataset (the players) at every step.

You could use a library that provides nearest neighbour searching.

I'm answering my own question because I have the answer now. Thanks to G. Samaras and Anony-Mousse: I use a kd-tree algorithm:

• First I build the tree with all the players
• Then for each player I calculate the list of all the players within given range arround this player

This is very fast and easy with the npm module kdtree: https://www.npmjs.org/package/kdtree

var kd = require('kdtree');
var tree = new kd.KDTree(3); // A new tree for 3-dimensional points
var players = loadPlayersPosition(); // players is an array containing all the positions
for (var p in players){ //let's build the tree
    tree.insert(players[p].x, players[p].y, players[p].z, players[p].username);
}

nearest = [];    
for (var p in players){ //let's look for neighboors
    var RANGE = 1000; //1km range
    close = tree.nearestRange(players[p].x, players[p].y, players[p].z, RANGE);
    nearest.push(close);
}

It returns nearest that is an array conataining for each player all his neighboors within a range of 1000m. I made some tests on my PC with 100,000 simulated players. It takes only 500 ms to build the tree and another 500 ms to find the nearest neigboors pairs. I find it very fast for such a big number of players.

bonus: if you need to do this with latitude and longitude instead of x, y, z, just convert lat, lon to cartesian x, y z, because for short distances chord distance on a sphere ~ great circle distance