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.

I am trying to calculate the average distance between any two nodes in an $r$-dimensional mesh.

This is a $3$-dimensional mesh with $n=3$ alt text

To choose any two points in the mesh there are $\left(n^r \left(n^r - 1\right)\right)/2$ ways of doing this.

So if we choose 2 points in the mesh $p\lbrace 1, 2, ..., r \rbrace$ and $q\lbrace 1, 2, ..., r \rbrace$ The distance is calculated as the Manhattan Distance

$\sum_{i=1}^{r} \left| {q_i - p_i} \right|$

Now i have to find the total distance between all nodes and divide that by the the number of ways of choosing two nodes (given above).

I know how to do this by looking at this 3-dimensional case which should work on the r-dimensional case also but i am having trouble expressing it in some sort of sum notation.

Here is how i think i can get the total distance between all nodes, i hope this is clear.

In this 3-d mesh let's assume the nodes are labelled $\left( 1, 1, 1 \right)$ to $\left( 3, 3, 3\right)$. Lets start at $\left( 1, 1, 1 \right)$ and sum up the distance between this node and all other nodes. Then we move to $\left( 1, 1, 2 \right)$ and sum up the distances between this node and all other nodes except for $\left( 1, 1, 1 \right)$ because we have already counted the distance between $\left( 1, 1, 1 \right)$ and $\left( 1, 1, 2 \right)$. Then we move onto $\left( 1, 1, 3 \right)$ and sum up all except for $\left( 1, 1, 1 \right)$ and $\left( 1, 1, 2 \right)$. We continue this until we permute through in order $\left( 1, 1, 1 \right)$, $\left( 1, 1, 2 \right)$, $\left( 1, 1, 3 \right)$, $\left( 1, 2, 1 \right)$, $\left( 1, 2, 2 \right)$, ect... Does that make sense?

That should give me the total distance without counting anything twice. Then i divide that by the number of ways of choosing 2 nodes and i will have the average distance. Does this sound correct to you? Any help would be appreciated.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

This approach is correct, but more work than required. Using the taxicab metric each dimension is independent. Taking a cube of side n you can count the vertical segments used as follows: from the bottom layer to the next layer up, we count $n^2$ (points on the bottom layer) times $n^2*(n-1)$ (points above the bottom layer) = $n^4*(n-1)$. For the next layer you have $2*n^2*n^2*(n-2)$ and so on. The $n^4$s distribute out and you can just think about the total distance along a line of length n. This is $\sum_{i=1}^{i=n}i*(n-i)$. Then multiply by $n^4$ and you have the total usage in the vertical direction. Then multiply by 3 for the total usage in each direction. And divide by the number of pairs of points, which you have calculated already. The extension to different number of dimensions or non-cubical meshes should be clear.

share|improve this answer
    
does this approach work for all values on n, not just n=3 in the example above? –  gprime Oct 18 '10 at 11:44
    
Yes, you just have to change some of the constants. The $n^4$ becomes $n^{(2*(r-1))}$ in r dimensions. The 3 to multiply by becomes r. And the number of points to divide by becomes the value you already calculated. –  Ross Millikan Oct 18 '10 at 15:43

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.