Proof wanted for task

Revision en1, by dino_merlin, 2023-05-09 23:12:36

The task in question is as follows: given N points on a coordinate plane, for some point A find the furthest point (manhattan disrtance) from A in the given set of N points. I know that one of the solutions to this problem is to consider only 4 points, the one with maximal (x + y) value, maximal (x — y) value, maximal (-x — y) value, maximal (y — x) value. It is guaranteed that one of these 4 points will be the furthest point from A. I can see that by doing this we maximize all of the 4 cases of the manhattan distance formula, but when we insert these 4 points into the formula it is not guaranteed that the corresponding cases we want to maximize will hold. Can anyone help me understand why this solution works?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dino_merlin 2023-05-09 23:12:36 760 Initial revision (published)