Shortest distance travel - common meeting point

Question

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 takes (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 :)

Answer 1

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