dino_merlin's blog

Proof wanted for task
By dino_merlin, history, 18 months ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Rotate the coordinates by 45 degrees. In the new coordinates, which are for example $$$u = x + y$$$ and $$$v = x - y$$$, the distance becomes $$$\max (|u|, |v|)$$$. Well, these particular coordinates are scaled by $$$\sqrt{2}$$$, but it's not important for the general idea.

→ Reply
»
18 months ago, # |
  Vote: I like it +4 Vote: I do not like it

For a more formal approach, look at what are $$$L^1$$$ and $$$L^{\infty}$$$ norms.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

To prove this, u just have to split the grid into four sections, where A is at the middle. consider the point furthest from A, call it B such that:

A.x <= B.x && A.y <= B.y. Then we know dist(A, B) = (B.x — A.x) + (B.y — A.y). Rearranging, we get (B.x + B.y) — (A.x + A.y). Since A.x, A.y are constant, we obviously have to maximise B.x + B.y, which corresponds to ur first maximal value (x+y).

If you do this for all four section of the grid, it should be obvious why this algorithm works.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This setup does not fully prove the solution as when you maximize the values it does not mean that the maz value will hold for every point. For example let's say that we have the 4 points(5,5), (5,-5), (-5, 5) and (-5, -5). If we want the distance from point (-4, -6), we can see that when we plug it into the distance formula with (-5, -5) we do not get -x — y.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it +40 Vote: I do not like it

      The Manhattan distance is $$$|x_1-x_2|+|y_1-y_2| =$$$
      $$$= \max(x_1-x_2, x_2-x_1) + \max(y_1-y_2, y_2-y_1) = $$$ $$$= \max(x_1-x_2+y_1-y_2, x_1-x_2+y_2-y_1, x_2-x_1+y_1-y_2, x_2-x_1+y_2-y_1)$$$.

      For each point, each of the $$$4$$$ cases produces one of the $$$4$$$ values in the last formula.

      Another interpretation is "if a value is wrong, we don't care because it's not optimal". For example, see 1473E - Minimum Path.

      → Reply