1
$\begingroup$

Having a graph of $n$ vertices in Euclidean $m$-dimensional space, is it possible to find average (Euclidean) distance between the vertices in $O(n)$ steps? Is there a deterministic algorithm for this?

1 Answers 1