# r-dimensional mesh question

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$

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 Answer

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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 31, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9415808916091919, "perplexity_flag": "head"}