Spacial clustering algorithm

Question

Given a collection of points on a 2D plane, I want to find collections of X points that are within Y of each other. For example:

8|
7|    a     b
6|
5|       c
4|
3|                    e
2|                  d          
1|
-------------------------
  1 2 3 4 5 6 7 8 9 0 1

a, b, c and d are points on the 2D plane. Given arguments of 3 for the number of points (X) and 3 for the distance (Y), the algorithm would return [[a, b, c]]. Some examples:

algorithm(X = 3, Y = 3) returns [[a, b, c]]
algorithm(X = 2, Y = 3) returns [[a, b, c], [d, e]] -- [a, b, c] contains at least two points
algorithm(X = 4, Y = 3) returns [] -- no group of 4 points close enough
algorithm(X = 5, Y = 15) returns [[a, b, c, d, e]]

Constraints:

• x and y axis (the numbers above) are both 10,000 units long
• there are 800 points (a, b, c, d etc) on the graph
• I don't think it matters, but I'm using JavaScript

---

Things I've tried:

• I actually care about outputting new points that are close to more than one input point, so I tried iterating on a grid and 'looking around' it using Pythagoras to find each point a given distance away. This is too slow given the total area. See the source here. You can also see the data size in real data test.
• DBSCAN, which seems to have a different purpose - I know how big I want my cluster size to be.
• I'm currently trying to compare points to each other and build up close pairs, then close triplets, etc, until the end, but this seems to be going down a bit of an inefficiency hole also. I'm going to continue and try some kind of hashing or dictionary to avoid these loops.

Answer 1

With only 800 points, you can probably just build the graph by comparing each pair, then run Bron--Kerbosch to find maximal cliques. Here's a legit-seeming Javascript implementation of that algorithm: https://github.com/SeregPie/almete.BronKerbosch