Given n points, choose a point in the given list such that the sum of distances to this point is minimum ,compared to all others.
Distance is measured in the following manner.
For a point (x,y) all 8 adjacent points have distance 1.
More clearer explanation.
A function foo is defined as
foo(point_a,point_b) = max(abs(point_a.x - point_b.x),abs(point_a.y - point_b.y))
Find a point x such that sum([foo(x,y) for y in list_of_points]) is minimum.
0 1 2 5 3 1 4 0
Eg: Distance between (4,5) and 6,7) is 2.
This can be done in O(n^2) time, by checking the sum of each pair. Is there any better algorithm to do it?