Finding 2D points reachable with short intermediate hops

Question

I have a list allNodes of around 60,000 nodes that correspond to 2D points. I'm constructing an adjacency list like

for(i in allNodes)
  for(j in allNodes)
    if(distance(i, j) <= 10) addEdge between i and j

and then performing a depth-first search from a set of sourceNodes to find the set of nodes reachable from sourceNodes. How can I make this faster than quadratic? I'm using C++.

Answer 1

The binning approach suggested by David Eisenstat's answer works if you expect points to be homogeneously distributed, which is not a property you specified about your data. Additionally, as noted, the Delaunay triangulation still requires local search on the induced graph to ensure that all nodes within the specified distance are found.

One way to get guaranteed performance is with a kd-tree. You can build one in O(2n log n) time (or faster if you don't care as much about guarantees and use randomization) and use it for performing range searches with a total time of O(2n√n).

It's unclear to me whether the Delaunay triangulation or the kd-tree would be faster in practice, but it seems to me that finding and using an appropriate kd-tree library would be a fast and simple solution, if you are worried about development time.