# 'Average Distance' Between Many Points

1. Jun 25, 2014

### Nlc11

Hello,
I want to find out the 'average distance' between many points on a 2D plain. That is, if you were standing on a point, what would be the average distance to all other points? For example, if there are three points A, B and C. AB = 5, AC = 10 and BC = 15, adding these up and dividing by three, we get 10. This is what I mean by the average distance.
Sort of like towns on a map. I'd like to be able to figure out an average distance between points. However, I don't actually know where any of the points are, just the size of the map and the number of points. My thinking is that there is a relationship between the size of a map and the distance between points on said map.
So far, I have made some progress. A 'strange' form of Pythagoras' Theorem can be used to find the 'average distance' between points. I have to note that I assume the points always spread out as far as possible. Apologies in advance, but I am new to LaTeX. It seems that:

$d = 2\sqrt{\frac{a}{p}}$

Where:
d = 'Average Distance'
a = area of shape
p = number of points

As a worked example:
Imagine a square, with side length 10 and there are two points. Going off the assumption that the points spread as far apart as possible, the two points will be on two opposite corners.
So, by Pythagoras' Theorem, they are 10√2 (14.14) apart.

$10√2 = \sqrt{10^2+10^2}$

In my equation so far:

$d = 2\sqrt{\frac{(10^2+10^2)}{2}}$

This also equals 10√2 (14.14).

With three points, I'm not sure how they would arrange. Possibly an equilateral triangle? Or two points on the vertices of one line and the other point in the middle of the opposite line (an isosceles triangle)? Either way, in the equation, it becomes:

$d = 2\sqrt{\frac{(10^2+10^2)}{3}}$

Which equals $\frac{20\sqrt{3}}{3}$ (11.54)

As I say, I'm not sure of the exact 'average distance', but this seems about right.

Now, if the shape is not a square. If we have a rectangle with lengths 5 and 10, and two points. Again, the two points will go in the opposite corners.

So, by Pythagoras' Theorem they will be:

$5√5 = \sqrt{10^2+5^2}$

In my equation:

$5√5 = 2\sqrt{\frac{(10^2+5^2)}{2}}$

So, the equation seems to work out. If anyone could confirm this, or at least point me in the right direction, I would be very grateful.

Edit:
So, a little more playing around revealed that the equation I made does not work out the 'average distance' between many points. I used the idea of a square ABCD, with points on A, B, C, D and one in the centre, which we will call point E. Again, the square will have side length 10. So the distance between AB, BC, CD and AD will be 10. The distance between AE, BE, CE and DE will be 5√2. Finally, the distance between AC and BD will be 10√2. So, a simple averaging will give us 4+4√2:

$4+4\sqrt{2} = 4(10)+4(5\sqrt{2})+2(10\sqrt{2})$

However, in the equation I specified earlier on, it equals 4√5:

$4\sqrt{5} = 2\sqrt{\frac{(10^2+10^2)}{5}}$

Okay, now I'm really stumped.
I imagine that there is a relationship between the area of a shape and the distributed points in the shape. I think that this will require calculus to do. Maybe the sum of every possible point divided by the area squared?

Last edited: Jun 25, 2014
2. Jun 25, 2014

### Simon Bridge

You are mistaken. Knowing only the size of the map and the number of points, you cannot know the distribution of the points.

Consider:
Using your analogy of a geographical map showing towns, the map may by of a section of the south Pacific showing a single archepelago ... so the points will be in a line (or a small clusetr) in the middle of the map, or it could be of the American Eastern Seaboard .... quite different.

Ergo - you also need to know the distribution of the points.
You will get different results if they are evenly distributed across the entire map or clumped in some way - say a sum of radial gaussians with different centers - or skewed (more likely along the eastern edge).

You need to factor in the distribution.

3. Jun 25, 2014

### Nlc11

Yes, that's why I always assume that the points are distributed as far apart as possible in the given space. That will effectively spread them evenly. I was only using the towns on a map analogy to make it clearer to understand, I'm thinking about just abstract points that are evenly distributed. I see what you mean. I should have phrased that better, more like 'a relationship between average distance between points and size of area if the points are evenly distributed'.

4. Jun 25, 2014

### Simon Bridge

Oh - if the points are distributed so each point is as far away as possible from each other - as if they were charges on an infinite sheet of charge, and you just looked at a finite section of that sheet, then it is probably a bit easier. Each point can be assigned an area, then it's like computing the mean distances between squares on a chessboard.

If the points are evenly distributed - but not necessarily as far apart as possible from each other - then the above approach could still work as an estimator ... if there are N points in area A then, on average, each point occupies area A/N.

Notice hat the average is going to be higher for a point closer to the edge of the map than close to the middle, so you will still get a distribution of average distances.

5. Jun 25, 2014

### Nlc11

Oh, I see.
You mentioned computing the mean distance between squares on a chessboard. How could this be done? Is there is simplified formula? Or is brute force calculation the only option i.e. counting the distances then manually averaging them?

6. Jun 25, 2014

### Simon Bridge

You would work out a strategy ... it's like working out the mean distance between points on a grid.

7. Jun 25, 2014

### Nlc11

Thank you very much.
Could you suggest a possible strategy?

8. Jun 25, 2014

### Simon Bridge

Exploit the symmetry of the chessboard/grid.
It becomes a combinations problem.

If you don't know how to do that, then start at the top-left corner and find all the distances systematicaly until you spot a pattern. This is something you will benifit from going through a bit of pain to learn about.

9. Jun 25, 2014

### Nlc11

Thank you for the help.

10. Jun 25, 2014

### Nlc11

I'm sorry, I don't know what you mean. I can see that the distances from the top left hand square to other squares are the same on the 'different sides' of the diagonal line (The squares running from top left to bottom right). For example the square 2 down and 1 across (from the top left sqaure) is the same distance as the square 2 across 1 down (from the top left square), so on and so forth. However, I don't see where this is going in terms of a formula to find the average distance between points.
Also, the average distance of a square from the top left square is about 6.188.
I just came across this thread (https://www.physicsforums.com/showthread.php?t=692866) which is quite similar to what I am trying to do. Effectively, it would be this, but just for any shape.