Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
This is a nice intuition! – dtldarek Apr 11 '12 at 0:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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