### kaldiuo's blog

By kaldiuo, history, 2 years ago, ,

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

 » 2 years ago, # |   +5 Oh, interesting trick. Can you give me a link to a problem that can be solved using this trick?
•  » » 2 years ago, # ^ |   +5
•  » » 2 years ago, # ^ |   +8
•  » » » 2 years ago, # ^ |   -37 Oh, thanks! I solved this problem, But it's not about max(|x1-x2|, |y1-y2|)
•  » » » » 2 years ago, # ^ |   +5 Actually it is.
•  » » » » » 2 years ago, # ^ |   -37 sanya, luchshe sotku verni
 » 2 years ago, # | ← Rev. 2 →   0 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, # |   +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.
•  » » 2 years ago, # ^ |   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).
 » 2 years ago, # |   +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).