Блог пользователя dino_merlin

Proof wanted for task
Автор dino_merlin, история, 18 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
18 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
»
18 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    18 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      18 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

      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.

      → Ответить