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

Manhattan distance trick in higher dimensions
Автор kaldiuo, история, 7 лет назад, По-английски

It is well known that given points (x, y) and you need to calculate the Manhattan distances between them, instead of using |x1-x2|+|y1-y2| you can first convert all points (x, y) into (x+y, x-y) and the distances will become max(|x1-x2|, |y1-y2|) (also known as Chebyshev distance). Can this trick apply to higher dimensions?

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Oh, interesting trick. Can you give me a link to a problem that can be solved using this trick?

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

Well, the unit circles in and are both squares (although one of them rotated and shrinked by ) and therefore isomorphic as stated in the question.

But, the unit circle in is an octahedron, while the unit circle in is just a regular cube. I don't see an elementary formal proof that this implies that there isn't a bijection with wanted properties in dimensions higher than 2, but intuitively it seems that this is the reason the trick doesn't work in higher dimensions.

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

    That's a nice way to see it! Maybe someone who deals with topology can help here? There may be some kind of non-trivial isomorphism between the 2 spaces (not exactly the aforementioned manhattan distance one).

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

IOI 2007 pairs. As I can remember, to solve this problem you should consider 4D space. Transform point (x, y, z) to the point (x + y + z, x + y — z, x — y + z, -x + y + z).

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

nice trick!! but do you have any proof for that? I thought about it but nothing came to mind

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

    suppose you have been given two 2-dimenstional points $$$(x1,y1)$$$ and $$$(x2,y2)$$$
    in the new coordinate system these points become $$$(x1 + y1, x1 - y1)$$$ and $$$(x2 + y2, x2 - y2)$$$
    for convenience let $$$a1 = x1 + y1$$$, $$$b1 = x1 - y1$$$, $$$a2 = x2 + y2$$$ and $$$b2 = x2 - y2$$$.
    the points in the new coordinate system are $$$(a1, b1)$$$ and $$$(a2, b2)$$$
    we have to prove that $$$|x1 - x2| + |y1 - y2| = max(|a1 - a2|, |b1 - b2|)$$$

    Consider the $$$RHS$$$

    $$$RHS = max(|a1 - a2|, |b1 - b2|)$$$

    substituting the values for $$$a1, a2, b1, b2$$$ we get
    $$$RHS = max(|(x1 + y1) - (x2 + y2)|, |(x1 - y1) - (x2 - y2)|)$$$

    $$$RHS = max(|(x1 - x2) + (y1 - y2)|, |(x1 - x2) + (y2 - y1)|)$$$

    to simplify this let $$$n = x1 - x2$$$ and $$$m = y1 - y2$$$
    We get $$$RHS = max(|n + m|, |n - m|)$$$

    We can also rewrite the $$$LHS$$$ in terms of $$$n \text{ and } m$$$ as $$$LHS = |n| + |m|$$$

    Now we have to prove $$$|n| + |m| = max(|n + m|, |n - m|)$$$

    This can be proven by considering the four cases

    case 1. $$$n >= 0, m >= 0$$$
    case 2. $$$n < 0, m >= 0$$$
    case 3. $$$n >= 0, m < 0$$$
    case 4. $$$n < 0, m < 0$$$

    → Ответить