1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – MPIchael
    Mar 3 at 13:55

2 Answers 2

Reset to default
2
$\begingroup$

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.

I'd recommend the use of the black-box FMM code here: https://github.com/ruoxi-wang/BBFMM3D.

Improve this answer
$\endgroup$
1
$\begingroup$

When calculating averages, you can iterate through all point connections and carry a counter, and the sum of the distances. You can overwrite any individual distance with the new ones. That way your memory footprint is minimal.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.