kaldiuo's blog

By kaldiuo, history, 2 years ago, In English,

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?

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

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Yes, it can be extended to n number of dimensions as seen in this problem http://www.spoj.com/problems/DISTANCE/.

6 Dimensions possible using all possible combinations of + — in place of |x1-x2|+|y1-y2|+...+|h1-h2| My accepted solution: https://ideone.com/obsrth

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
2 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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).