Shortest distance - common meeting point

Question

I ran into this problem when there are several houses on the two-dimensional grid (their coordinates are indicated), and we, in fact, have to find which house can be used as a meeting point so that the distance traveled by each is minimized. Suppose that the distance along the x or y axis takes 1 unit, and the distance to the diagonal neighbors takes (say) 1.2 units.

I can’t think of a good optimization algorithm for this.

PS: Not a homework problem. And I'm looking for an algorithm (not code) and, if possible, its proof.

PS # 2: I'm not looking for an exhaustive solution. Believe it or not, it struck me :)

Answer 1

, . , :

E|X-c| >= E|X-median(X)| c.

:
https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315

Answer 2

, , , , . ( ) distance, . . , , - . - .

Answer 3

. , sqrt (2) ~ = 1.41 , , , .

( ), , (x) + (y) .

1D, , . /, , 5 , .

, , . , 4- , 3 , 2 , 1. 4- , 4 , , 3. . .

, , .

Answer 4

. , : (mx, my) , , N, . , , .

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

x y. , x y. , ^^ , , , (mx, my) , . , , (mx, my) (xi, yi) , (xi, yi) , () . :

, x- ( ) X1<X2<...<Xn. Xj<mx<X(j+1), j = N/2, mx , mx' <- mx-1. , d' = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1| , mx-1 N/2 ( k >= j + 1 <= j), , . (mx-1, my) . , Xj<mx<X(j+1) Yj<my<Y(j+1), . , , .

/ , , , .

, .

Answer 5

Your problem is called Optimal meeting point search. The following work gives an effective approximate algorithm http://www.cse.ust.hk/~wilfred/paper/vldb11.pdf

Answer 6

Well, you could overcome it. Take each house and calculate the distance to each other. Summarize the distances for each individual house. Then just take the house with the lowest amount.