# Calculate average distance between pairs of points without computing full distance matrix

Suppose I have a set of $$N$$ points of shape $$N \times D$$, where $$D$$ is the dimensionality. I want to compute the average Euclidean distance between all points, as well as additional moments such as the variance, median, and percentile boundaries.

Is there a way to calculate or estimate these quantities without finding the full $$N \times N$$ distance matrix? I am hoping for a solution that requires less than $$\mathcal{O}(N^2)$$ memory.

• Do you have any a-priory knowledge of the point cloud? I mean thinks like absolute bounding box or if they are clustered or more homogeneously spread? What language are you working in? Mar 3, 2022 at 13:55

You can do this in $$\mathcal{O}(N)$$ time (and memory) using a fast multipole algorithm that can handle nondecaying kernel functions such as the distance function $$d(\mathbf{x},\mathbf{y})=|\mathbf{x}-\mathbf{y}|$$.
The average distance is given by $$\frac{1}{N^2}\sum_{i=1}^{N}\sum_{j=1}^{N} d(\mathbf{x}_i,\mathbf{x_j})$$. The inner sum can be evaluated at each $$\mathbf{x}_i,i=1,\ldots,N$$ in a total of $$\mathcal{O}(N)$$ time, and the outer sum over $$i$$ can also be computed in $$\mathcal{O}(N)$$ time.