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

2

This is not a proof, but maybe an indication that a positive answer is unlikely. In $2$ dimensions, consider the $2N+2$ points $(j,0)$ and $(0,j)$ for $0 \le j \le N$. The average distance $\overline{D}$ will be a linear combination over $\mathbb Q$ of $\sqrt{a^2 + b^2}$ for all pairs of positive integers $(a,b)$ with $a,b \le N$. In particular note that each prime $p < N^2$ with $p \equiv 1 \mod 4$ can be expressed as $a^2 + b^2$, so $\overline{D}$ will include terms in $\sqrt{p}$ for such primes, of which there are on the order of $N^2/\log N$. Now it is known that these $\sqrt{p}$ are linearly independent over the rationals, and indeed that $\sqrt{p}$ is not in the field generated by the square roots of the other primes. I suspect (but again, I have no proof) that any algorithm to calculate $\overline{D}$ using integers, $\sqrt{},+,-,\cdot, /$ would require at least $\Omega(N^2/\log N)$ square root operations.

  • 0
    This is a nice intuition!2012-04-11