Mean distance between points of 2D array

1. Jun 17, 2014

cosmik debris

Say I have an N X N array of points, I would like a formula to give the mean distance between the points. There are lots of short distances but only two long ones (diagonal). There are plenty of algorithms to do this but I would like to work out a formula if there is one. Can someone point me in the right direction?

Thanks

2. Jun 17, 2014

Simon Bridge

You know how to find the distance between any two points right?
To get the mean distance, find the distances for every possible pair of points, add them up, and divide by the number of pairs.

3. Jun 17, 2014

cosmik debris

Yeah I know how to calculate the distances, and I meant median not mean.

4. Jun 18, 2014

Simon Bridge

I that case you need to also rank the distances.
To my knowledge there is no "equation" that will do that.

The median is so that the number of data points above and below is the same.

5. Jun 19, 2014

.Scott

My initial thoughts:
Number of points will be N², so number of distances will be N²(N²-1)/2.
So if theses distances were sorted by length, the one you would be looking for would be near N²(N²-1)/4.
As it turns out, N²(N²-1)/4 is always an integer, so it will always be possible that to get the median, you will be averaging between two values.

The number of distances of value 1 will be: 2·N(N-1)
The number of distances of integer value M will be: 2·N(N-M)
The number of distances of √2 will be 2·(N-1)²

Skipping to infinity:
When N is very large, the median distance between a corner point and all other points would be the radius of an arc that divides the square into equal areas: √(2N/π)
In contrast, a point near the center would be half that: √(N/2π)

Don't have time for more thinking right now.

Nasty problem.

6. Jun 19, 2014

cosmik debris

Yes it's tricky. We managed to get a closed form solution for the continuous case and as it turns out it did give us an insight into our problem. In case you're interested; this is a massive MIMO investigation. We were trying to compare a linear array of antennas to a square array. It turns out that a linear array say 10m long is equivalent to a square array of about 6m X 6m, not really any improvement.