4
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    does this approach work for all values on n, not just n=3 in the example above?2010-10-18
  • 0
    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.2010-10-18