Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
    
This is a nice intuition! –  dtldarek Apr 11 '12 at 0:14
add comment

Your Answer

 
discard

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.