All points with minimum Manhattan distance from al

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

Since in manhattan distance each component contributes separately, you can consider them separately too. The optimal answer is ( median(x),median(y) ). You need to look around this point for integer solutions.

NOTE: I did not read your question properly while answering. My answer still holds, but probably you knew about this solution already.

Answer 2

If the median gives you an interval of the order of 10^9 then each point in that interval is as good as any other.

So depending on what you want to do with those points later on you can either return the range or enumerate points in that range. No way around it..

Obviously in two dimensions you'll get a bouding rectangle, in 3 dimensions a bounding cuboid etc..

The result will always be a cartesian product of ranges obtained for each dimension, so you can return a list of those ranges as a result.

Answer 3

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.

Answer 4

Yes i also think that for odd number of N points on a grid , there will be only a Single point(i.e the MEDIAN) which will be at minimum sum of Manhattan distance from all other points.

For Even value of N, the scenario will be a little different.

According to me if two Sets X = {1,2} and Y= {3,4} their Cartesian product will be always 4.

i.e X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}. This is what i have understood so far.

As for EVEN number of values we always take "MIDDLE TWO" values as MEDIAN. Taking 2 from X and 2 from Y will always return a Cartesian product of 4 points.

Correct me if i am wrong.