All points with minimum Manhattan distance from all other given points [Optimized]

Question

The problem here is to find set of all integer points which gives minimum sum over all Manhattan distances from given set of points!

For example:

lets have a given set of points { P1, P2, P3...Pn }

Basic problem is to find a point say X which would have minimum sum over all distances from points { P1, P2, P3... Pn }.

i.e. |P1-X| + |P2-X| + .... + |Pn-X| = D, where D will be minimum over all X.

Moving a step further, there can be more than one value of X satisfying above condition. i.e. more than one X can be possible which would give the same value D. So, we need to find all such X.

One basic approach that anyone can think of will be to find the median of inputs and then brute force the co-ordinates which is mentioned in this post

But the problem with such approach is: if the median gives two values which are very apart, then we end up brute forcing all points which will never run in given time.

So, is there any other approach which would give the result even when the points are very far apart (where median gives a range which is of the order of 10^9).

Answer 1

You can consider X and Y separately, since they add to the distance independently of each other. This reduces the question to finding, given n points on a line, a point with the minimum sum-of-distances to the other points. This is simple: any point between the two medians (inclusive) will satisfy this.

---

Proof: If we have an even number of points, there will be two medians. A point between the two medians will have n/2 points to the left and n/2 points to the right, and a total sum-of-distances to those points of S.

If we move it one point to the left, S will go up by n/2 (since we're moving away from the right-most points) and down by n/2 (since we're moving towards the left-most points), so overall S remains the same. This holds true until we hit the left-most median point. When we move one left of the left-most median point, we now have (n/2 + 1) points to the right, and (n/2 - 1) points to the left, so S goes up by two. Continuing to the left will only increase S further.
By the same logic, all points to the right of the right-most median also have a higher S.

If we have an odd number of points, there is only one median. Using the same logic as above, we can show that it has the lowest value of S.