The challenge
Given $n$ points in $\mathbf{R}^3$ and a cutoff distance, $d$, I would like to determine
- all pairs of points that are separated by less than the given cutoff distance, $d$, and
- all pairs of points that can be connected by less than 5 segments taken from the list of pairs from above.
While this is straight-forward for small $n$, for large $n$ the simplistic approach given below is slow (searching for the pairs) and memory consuming (GraphDistanceMatrix seems to return a dense matrix). How could this problem be solved efficiently for $n$ of order 30000?
Inefficient sample code:
Generate sample data:
n = 1000; (* desired: n=20000 *)
pos = RandomReal[{0, n^(1/3)-1}, {n, 3}];
Find close points (ad 1):
d = 0.8;
connected = Select[Subsets[Range[n], {2}], (Norm[pos[[#[[1]]]] - pos[[#[[2]]]]] < d)&];
Pairs of points closer than 5 leaps apart (ad 2):
v = Union[Flatten[connected]];
g = Graph[v,UndirectedEdge @@@ connected];
gdm = GraphDistanceMatrix[g, 4];
ind =
Select[Position[gdm, Alternatives[1, 2, 3, 4], {2}], (#[[1]] < #[[2]])&] /.
Thread[Range[Length[v]] -> v];