Shortest distance travel - common meeting point

I came across this problem wherein there are a number of houses on a 2-D grid (their coordinates are given) and we essentially have to find which house can be used as a meeting point so that the distance traveled by everyone minimizes. Let us assume that a distance along the x or y-axis takes 1 unit and a distance to the diagonal neighbors ta开发者_如何学Gokes (say) 1.2 units.

I cannot really think of a good optimization algorithm for this.

P.S: Not a homework problem. And I am only looking for an algorithm (not code) and if possible, its proof.

P.S #2: I am not looking for the Exhaustive solution. Believe it or not, that did strike me :)

As already pointed, in case of Manhattan distance the median gives a solution. This is an obvious conclusion from the well-known fact that median minimizes the mean of absolute deviation:

E|X-c| >= E|X-median(X)| for any constant c.

And here you can find an example of the proof for discrete case:
https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315

This is probably really inefficient, but loop through all the houses, then loop through all the other houses. (nested for loops) Use the distance formula to find the distance between the 2 houses. Then you have the distance between every house. One quick and easy way to find which house is the closest distance is to add everyone's walking distance together for the given house. The house with the least total walking distance is the meeting area of choice.

I have been bugged by the same problem for some time now. The solution is the obvious consensus given in earlier posts: find the median (mx, my) independently and then find the point closest in the given N points and that is the meeting place. To see why this is actually the solution you should first consider the distance.

d = sum(|xi-x|) + sum(|yi-y|) over all 1<=i<=N,

which is independent in x and y. Hence we can solve the 1-D case for x and y. I will skip over the explanation given ^^ and hence conclude that (mx,my) is the best solution if we consider all possible points.The bigger challenge is to prove that we may move from (mx, my) to the closest (xi,yi) such that (xi, yi) is one of the given points, w/o changing(increasing) the distance. The proof goes:

Consider that we have sorted x-coordinates( for sake for proof ) and that X1<X2<...<Xn. Also Xj<mx<X(j+1) where j = N/2, now let's move mx one step to left, that is mx' <- mx-1. Hence d' = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1| We know that mx-1 will increase N/2 values( for k>=j+1 and decrease for <=j ) hence the effect is the same. Thus (mx-1, my) gives the same solution. It means that there is a space from Xj<mx<X(j+1) and Yj<my<Y(j+1) where the distance does not change. Thus we can find the closest such point which is the answer.

I have ignored the subtle case of even/odd nodes, but I hope the math works out itself when you realize the basic proof.

This is my first post, do help me improve my writing skills.

Your distance metric is weird. You'd expect that travelling on the diagonal should take at least sqrt(2) ~= 1.41 times the distance of travelling along a component direction, because that's how much further it is if travelling in a straight line along the diagonal by the Pythagorean theorem.

If you insisted on a manhattan distance (no diagonals allowed), then you'd want to pick the house closest to the median(x) + median(y) of the houses.

Consider the 1D case, you have a bunch of points on a line, and you want to pick the meeting spot. For concreteness/simplicity, let's say there are 5 houses, none duplicate.

Consider what happens as the meeting spot drifts away from the median to the right. For every unit away until you pass the 4th house left to right order, 3 people have to take an additional step to the right, and 2 people have to take one less step to the left, so the cost goes up by 1. Once you pass the 4th house, then 4 people have to taken an additional step to the right, and a single person has to take one less step to the left, so the cost increases by 3. An identical argument holds as you move the meeting spot to the left from the median. Moving away from the median always increases the cost.

The argument generalizes to any number of people, with or without duplicate houses, and even across to arbitrary number of dimensions, so long as you aren't allowed to use the diagonal.

Your problem is called Optimal Meeting Point Finding. The following paper gives an efficient approximate algorithm http://www.cse.ust.hk/~wilfred/paper/vldb11.pdf

Well, you could brute force it. Take each house and calculate the distance to each other house. Sum the distances up for each individual house. Then just grab the house that had the lowest sum.