Finding the maximum distance between coordinates (x, y)

Question

Im trying to calculate the maximum distance in Manhattan of a large two-dimensional input, the inputs are composed of (x, y) s and what I want to do is to calculate the maximum distance between these coordinates in less than O (n ^ 2) time, I can do it in O (n ^ 2), going through all the sth elements as:
* (The Manhattan distance between two points (X1, Y1) and (X2, Y2) is: | X1-X2 | + | Y1-Y2 |)

for ( 0 -> n ) for ( 0-> n ) { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum } 

but it will not work efficiently for very large inputs :(
anyone have an idea for a better algorithm?

Answer 1

Only two cases are considered, if we consider only such results that Xi <= Xj .

• If Yi <= Yj , then the distance (Xj + Yj) - (Xi + Yi)
• Otherwise, the distance (Xj - Yj) - (Xi - Yi)

By dividing it into these cases, I got rid of the absolute value function, which greatly facilitates the explanation of distances.

So, we just select the points with minimum and maximum x+y and calculate the distance. Then select the points with minimum and maximum xy and calculate the distance. One of these two distances is your maximum.

This can be done in O(n) , which is asymptotically optimal.

Answer 2

It is quite simple and can be calculated in O(n)

Let x1>x2 and y1>y2

 max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2) 

Let x1>x2 and y1<y2

 max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2) 

Now change x1 to x2 and you will get the same results.

So in general, your decision

 max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) ) 

Answer 3

The best thing you can do with such questions is to try to establish small results that will help you deal with a common problem.

For example, it is not difficult to determine that for any three points A, B and C that have the condition that B is between (more on this per second) A and C, B will never be more from the fourth point D than one of A and C. With the standard Euclidean distance metric, a point is located between two other points if it lies on the segment connecting them. For Manhattan measurements, this is not so simple - partly because the concept of a segment is not well understood.

A more general way of describing “between” is (using the notation that the distance from A to B is | AB |): Point B is between two points A, C if | AB | + | BC | = | AC |

You can see that at Euclidean distance this means that B lies on the segment connecting A and C.

At a Manhattan distance, this means that point B is contained in a rectangle defined by A and C (which, of course, can be a straight line segment if AC is parallel to one of the axis).

This result means that for any point, if it lies between two existing points, it cannot be more from any new points that are added to the set than those that surround it.

Now this information does not solve the problem for you, but it allows you to discard many potential future calculations. Once you have determined that the point is between the other two, it makes no sense to track it.

Thus, you can solve this problem only by tracking external points and not paying attention to what gets inside.

An interesting exercise for the casual observer

Prove that you can have no more than 4 different points, so that none of the points is between the other two in the sense of Manhattan.

With this second result, it becomes clear that you will only need to track up to 4 points.

Some of the methods already presented are probably faster, but this method is more fun!

Additional loan

Summarize these ideas in n dimensions

Answer 4

The first big improvement would be:

 for ( X: 0 -> n ) for ( Y: X -> n ) { compute the distance between X and Y } 

since the distance between X and Y is the same as the distance between Y and X. This will cut your calculations by half ...

Answer 5

The maximum distance will be between the farthest points from each other. So you just find the point with maximum X and maximum Y, and then find the point with minimum X and minimum Y and calculate the distance between them. There may be many points that will meet the criteria .. but at least you will have far fewer points to check