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

Question

The challenge here is to find the set of all integer points that give the minimum sum over all Manhattan distances from a given set of points!

For example:

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

The main problem is to find a point, say, X, which would have a minimal sum at all distances from the points {P1, P2, P3 ... Pn}.

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

Moving a step further, there may be more than one value of X satisfying the above condition. that is, there may be more than one X that would give the same value of D. So, we need to find all such X.

One basic approach that anyone can think of is to find median information and then brute force, the coordinates mentioned in this post

But the problem with this approach is this: if the median gives two values ​​that are very different, then we end up with a rough coercion of all points that will never be executed at a given time.

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

Answer 1

If the median gives you an interval of the order of 10 ^ 9, then every point in this interval will be as good as any other.

So, depending on what you want to do with these moments later, you can either return the range or list the points in that range. In no case.

Obviously, in two dimensions you get a bouding rectangle, in 3 dimensions a bounding cube, etc.

The result will always be the Cartesian product of the ranges obtained for each measurement, so you can return a list of these ranges as a result.

Answer 2

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

---

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

If we move it one point to the left, then S will go up by n / 2 (since we are moving away from the right points) and down by n / 2 (since we are moving to the left), so the overall S remains unchanged. This is true until we reach the leftmost median point. When we move one left side of the leftmost median point, we now have (n / 2 + 1) to the right, and (n / 2 - 1) points to the left, so S rises by two. Continuation to the left will only increase S.
By the same logic, all points to the right of the rightmost median also have a higher S.

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

Answer 3

Since at a distance in Manhattan each component contributes separately, you can consider them separately. The optimal answer is (median (x), median (y)). You should look around this point for integer solutions.

NOTE I did not read your question correctly when answering. My answer is still valid, but you probably already knew about this solution.

Answer 4

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

With an even N, the scenario will be slightly different.

For me, if two sets are X = {1,2} and Y= {3,4} , their Cartesian product will always be 4.

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

Regarding the EVEN value, we always take the “MIDDLE TWO” value as MEDIAN. Taking 2 from X and 2 from Y always returns the Cartesian product of four points.

Correct me if I am wrong.