Posted: 7/28/2010 9:20:17 PM EDT
|
Here's a problem for all the geeks out there...
Say I have an arbitrarily sized grid (X x Y). Given a set of N points on the grid, I'd like to find the single point P which is the shortest distance to all N points. In other words, if you plotted all N points on the grid, point P would be the geographic center. Keep in mind that there could be multiple points with the same coordinates, so they need to be treated as weighted points. etc. Any ideas as to a formula or algorithm I should use? I'm sure it's something simple... on the other hand, I've been drinkin! Edited to add: I've already got the brute force method, which is to take every possible grid point (x,y) and calculate distances to each point, producing a sum. So it's not the prettiest method, but it works. |
|
My brain's fried right now, but a bit of real analysis makes me think that your solution would be the average of the X coordinates and the average of the Y coordinates.
Or at very least the (X,Y) coordinate that is closest to the average of the X and Y coordinates if point P has to have integer coordinates. |
|
Quoted:
My brain's fried right now, but a bit of real analysis makes me think that your solution would be the average of the X coordinates and the average of the Y coordinates. Or at very least the (X,Y) coordinate that is closest to the average of the X and Y coordinates if point P has to have integer coordinates. Dunno about that... Imagine you have 10 points. 9 of them are 1" away from you, the 10th is on the moon. Averaging out how far they are from you would leave you a LONG way to go... but the closest point to all points will be somewhere near the 9 that are near you (only the one on the moon will make a long line, instead of 9 making a long line). |
|
Quoted: My brain's fried right now, but a bit of real analysis makes me think that your solution would be the average of the X coordinates and the average of the Y coordinates. Or at very least the (X,Y) coordinate that is closest to the average of the X and Y coordinates if point P has to have integer coordinates. What he said if they're weighted: Xavg=(X1+X2+X3.+..+Xn)/n Yavg=(Y1+Y2+Y3.+..+Yn)/n Weighted average coordinates are (Xavg,Yavg) If you're looking for the geographic center the weighting of the sample doesn't matter as spatial coordinates are constant for the purposes of this problem. In that case the center of the sample would occur where: Cmax=sqrt[(Xb-Xa)2+(Yb-Ya)2] and would occur at a point halfway between X-coordinates with the largest difference and halfway between the Y-coordinates with the biggest difference. |
|
Lemme mathturbate for a bit, and pardon any errors in notation.
I see how that would conceptually make sense, but I'm still not seeing the error in the mathematics. How's this: let Xm, Ym be the coordinates for P. let f(X, Y) be the sum of the distances. want to minimize f(X, Y), and that would happen at f(Xm, Ym). f(Xm, Ym) = SUM( SQRT( (Xi - Xm)^2 + (Yi - Ym)^2 ) ) same as minimizing SUM ( (Xi - Xm)^2 + (Yi - Ym)^2 ) Expand and take partial derivatives WRT to X and Y. Set = 0 and find that Xm, Ym are the means of the Xi, Yi. |