kaldiuo's blog

By kaldiuo, history, 21 month(s) 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

»
21 month(s) 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?

»
21 month(s) 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

»
20 months 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.

  • »
    »
    20 months 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).

»
20 months 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).