"Mid-point" of a set of points

backboiler

Given a set of points in 2-D space, how do you go about finding the "mid-point" of that set. I'm not altogether clear as to the properties of this "mid-point" but if I define it as that point that results in the smallest sum of distances to each other point, that'd be a start.

The background to this is that a couple of years back the company I worked for was moving office. I thought it would be an interesting experiment to see where the best location for a new office would be, geographically speaking. In reality, of course, these things are decide by rates of rent and where the senior managers live but it'd still be interesting to see how mathematics would solve this. Maybe my shortest total travel distance idea isn't appropriate. I'm not talking about taking into accound the route that roads take or one-way streets now, just a clean theoretical plane.

For two points it's trivial enough to get the mid-point of the line between them, but as points get added the calculation becomes harder to figure out. If we have, say, 30 points how does the calculation go?

Thomas_S_Hunterson

It's very much like calculating the average of the co-ordinates. The term mid-point isn't really correct for this application however, but I think I know what you're getting at.

For, say, a set of co-ordinates on an X,Y plane it would be the sum of the x values divided by the number of values and the sum of the y values divided by the number of y values, if you understand me?

Fremen

It's very much like calculating the average of the co-ordinates. The term mid-point isn't really correct for this application however, but I think I know what you're getting at.

For, say, a set of co-ordinates on an X,Y plane it would be the sum of the x values divided by the number of values and the sum of the y values divided by the number of y values, if you understand me?

I don't think that's correct. Imagine nine points very close to (0,0) in the plane, and one point at (100,100). Then the 'average' would be close to (10,10). The total euclidean distance (square root of the sum of the squares of the co-ords) is roughly (9 * 14) + (1 * 127) = 254
However, if the centerpoint was very close to (0,0), the total distance becomes close to 141.

backboiler

Sean_K,
I had originally thought the same - that it'd be as easy as a pair of averages - but it just doesn't seem to give the right answer. Fremen's example seems to prove that.
I agree with you that mid-point isn't the right word (that's why I double-quoted it) but a better one wasn't coming to mind. Probably if I had the correct word, a quick web search would give an immediate answer.

From my rapidly fading recollection of these kinds of things I have a feeling that it could turn into a N-dimensional differentiation for a set of N points but, again, I have no sound mathematical reasoning to show this.

Fremen

yeah, it should do. If you have N points labeled (a_i, b_i) for different integers i, then the total distance from a point (x,y) to the set is

SUM_OVER_i ( SQUARE_ROOT ( (x - a_i)^2 + (y - b_i)^2))

Presumably you can find a local minimum for this function through differentiation with respect to x and y

MathsManiac

backboiler wrote: »

For two points it's trivial enough to get the mid-point of the line between them, but as points get added the calculation becomes harder to figure out. If we have, say, 30 points how does the calculation go?

But the midpoint of two points doesn't correspond to the n=2 case of your generalised "midpoint", by the way. If you're looking for a point such that the sum of the distances is minimised, this is not uniquely defined for the case n=2, since any point on the segment yields the same sum of distances to the two points.

In the case n=3, you're looking for the point whose sum of distances to the three vertices of a given triangle is minimised. This is called the Fermat point of the triangle. This is an interesting geometrical investigation using a dynamic geometry software package. When people find the right point by trial and error, they may observe that the lines to the vertices make angles of 120 degrees with each other. Not so easy to spot is how to construct this point: construct an equilateral triangle on each side, and then join the remote corner of each new triangle to the opposite corner of the original triangle. These lines intersect at the Fermat point. If any of the angles of the original triangle is greater than 120, it's a degenerate case, with the Fermat point being at that vertex.

In general (i.e. for n>=3 points) the point you're talking about is called the geometric median. Wikipedia has an entry for it: http://en.wikipedia.org/wiki/Geometric_median