Efficient algorithm for estimating the correlation dimension from a set of discrete points

We present an algorithm which computes the standard Grassberger-Procaccia correlation dimension of a strange attractor from a finite sample of N points on the attractor. The usual algorithm involves measuring the distances between all pairs of points on the attractor, but then discarding those distances greater than some cutoff $r_0$. Our idea is to avoid computing those larger distances altogether. This is done with a spatial grid of boxes (each of size $r_0$) into which the points are organized. By computing distances between pairs of points only if those points are in the same or in adjacent boxes, we get all the distances less than $r_0$ and avoid computing many of the larger distances. The execution time for the algorithm depends on the choice of $r_0$, the smaller $r_0$, the fewer distances to calculate, and in general the shorter the run time. The minimum time scales as O(NlogN); this compares with the O($N^2$) time that is usually required. Using this algorithm, we have obtained speedup factors of up to a thousand over the usual method.