The Middle Of Several Locations

August 29, 2006 2:00 PM

If I have 3 or more locations on a map, how can I find the nearest point to all the locations?

In others words if I am given several geographic locations how can I find the point that is central to all locations? And more importantly, is there a way to do this with google maps or yahoo maps or some other such service?

posted by hubs to science & nature (14 comments total)

You can't necessarily find a "central" point for more than three locations. Here's the answer for three points, with a generalization in case you ever find yourself in an n-dimensional hyperspace. This will help you out if you're unfamiliar with the notation.
posted by mr_roboto at 2:19 PM on August 29, 2006

You can search for "the minimum enclosing circle problem". Once you find the smallest circle that encloses all the points, you can find the centre of that circle. I don't know if anyone has done this sort of thing with Yahoo Maps or Googel Maps.
posted by chunking express at 2:21 PM on August 29, 2006

You probably mean the point which has the minimal total distance to the locations.
Draw lines that connects the points creating an outside perimeter (for example, three points = triangle). For each internal angle, draw a line that bisects that angle into two equal angles. If you do this for each of the points, those bisecting lines will meet at the geographic center.
posted by dances_with_sneetches at 2:22 PM on August 29, 2006

Keep in mind that you're on a sphere. The geometry is slightly different.

Instead of throwing straight lines all over the place, you should be throwing great circles aka "geodesics".
posted by maschnitz at 2:22 PM on August 29, 2006

Sounds like you're not really after Old Skool, but have some anyway :-)

With the three points on a paper map or print-out, it's pretty trivial to use a straight-edge and compass (the circle-drawing kind) to determine the point central to all. (draw a line between each, resulting in a triangle. Use the compass to bisect each line and draw a line from the bisect-cut to the remaining (far) point. Where those lines intersect is your central point. If they don't quite intersect (ie, you've been sloppy), just use the centre of the tiny triangle they create. Note that at the continental scale, you'd want to do this on a globe rather than on a flat (and thus projection-distorted) sheet.

With more points, you could do the same thing, but you won't get a nice intersection, you'll get an n-gon, the centre of which is your central point, ie, it's an estimate that you can recurse for greater accuracy. There is no doubt a better way, but I'd have to think about it for a while :)
posted by -harlequin- at 2:25 PM on August 29, 2006

If there is a Google Maps tool, it might be here.
posted by beagle at 2:33 PM on August 29, 2006

The simplest way to do something like this would be to find the barycentre of the points, which (if you're willing to treat all the points as lying on a grid) has as its longitude the average of the longitudes of all the points, and similarly for the latitude. It turns out that the barycentre is the point such that the sum of the squares of the distances to the points is minimized, not the sum of all the distances, but that's a minor cavil.

Once you've got the longitude & latitude of the barycentre, it shouldn't be too hard to map it on your online mapping tool of choice.
posted by Johnny Assay at 2:34 PM on August 29, 2006

Could you average their latitudes and their longitudes together? I used this technique to approximate the best location for a move using weighted values for the various coordinates (work, friends, family, etc.) based on how many times I made the trip per week.

It probably wouldn't work well if the distances were on the scale of hundreds of mile (or near the poles).
posted by justkevin at 2:35 PM on August 29, 2006

If they're not too far apart, perhaps the gmap pedometer can help. (It's great for figuring out jogging/biking routes or figuring out how far you actually went on your rambling bike ride or walk.)
posted by Cranialtorque at 2:45 PM on August 29, 2006

Geometry is nice, but that assumes that everyone can travel "as the crow flies." Unfortunately, roads may be a bit more indirect than straight lines to a central point.
posted by bim at 3:09 PM on August 29, 2006

Thanks everyone, it seems there is more than one correct answer to my problem and definately some verying degrees of accuracy and other issues - such as the crow-flies issue - that hadn't occured to me.

I'm constantly astounded by the level of thought and information found on askmefi. What a great group we have here. Thanks everyone.

If anyone cares I'll probably end up using the simple minimum enclosing circle method since I was just trying to find a good meeting place for a biking club. But I learned a lot today, and thats what counts in my book!
posted by hubs at 3:25 PM on August 29, 2006

It sounds like the average-of-the-coordinates solution is the easiest one...is it the most accurate? Johnny Assay, your comment made it sound like it's a good approximation, but not perfect. Are there any cases where averaging the coordinates would not produce the point that minimizes the total distance between it and all of the starting points?
posted by molybdenum at 6:22 PM on August 29, 2006

Are there any cases where averaging the coordinates would not produce the point that minimizes the total distance between it and all of the starting points?

Yes, very definitely. There's one example that's easy to visualize which demonstrates the difference between the average coordinates (which, as Johnny Assay notes, minimizes the sum of the squares of the distances), and the point which simply minimizes the sum of the distances.

Suppose you have several people all within a small area (let's say they all live on the same city block), and one outlier, a person who lives several miles away.

If you choose the point which minimizes the sum of the distances, that point will be within the city block where everyone but one person lives. Moving the point beyond that block is not optimal, as you are decreasing the distance which needs to be travelled by one person by however much you move that point, but increasing the distance travelled by several people by (roughly) that same amount.

If you choose the "average coordinates" method, minimizing the sum of the squares of the distances, the point may be outside the one city block, in the direction of the loner. How much outside the block depends on how many people are inside the block--the more people in the block, the closer to the block your point will be.

Another, related example: suppose you have a group of people that live in two cities, and the two cities are some distance from each other. Let's say your group has 201 people--100 live in city A, and 101 live in city B. "Minimize the total distance" will likely result in a point within city B. "Minimize the sum of the squares of the distance" will result in a point just about halfway between A and B, but just slightly closer to city B.

Another point to keep in mind is that "minimize the total distance" does not necessarily result in a unique solution. This is easiest to visualize when you have just two people: any point along the line segment joining the two has an equal, and minimal, total distance to the two points. The same can happen when you have more than two people, although it may be harder to visualize. "Minimize the sum of the square of the distances" always gives a unique solution. To take a variation of my second example above, if you have 100 people in city A and 100 in city B, any point along the road between A and B would give an equally good, minimal solution under the "minimize total distance" criterion (I'm oversimplifying, of course; taking into account exactly where the people live within each city might result in a unique solution), but only the point halfway between A and B is optimal under the "minimize the sum of the squares of the distances" criterion.
posted by DevilsAdvocate at 9:02 AM on August 30, 2006

P.S. My comments about the minimal-sum-of-squares method producing a unique solution assume both Euclidean geometry and the standard Euclidean measure of distance. If either of these do not hold, it's possible (though unlikely) that there are multiple equally good solutions.
posted by DevilsAdvocate at 9:09 AM on August 30, 2006