### kaldiuo's blog

By kaldiuo, history, 6 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

| Write comment?
 » 6 years ago, # |   +5 Oh, interesting trick. Can you give me a link to a problem that can be solved using this trick?
•  » » 6 years ago, # ^ |   +5
•  » » 6 years ago, # ^ |   +8
•  » » » 6 years ago, # ^ |   -37 Oh, thanks! I solved this problem, But it's not about max(|x1-x2|, |y1-y2|)
•  » » » » 6 years ago, # ^ |   +5 Actually it is.
•  » » » » » 6 years ago, # ^ |   -37 sanya, luchshe sotku verni
 » 6 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.
•  » » 6 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).
 » 6 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).
 » 7 weeks ago, # |   -32 nice trick!! but do you have any proof for that? I thought about it but nothing came to mind
•  » » 7 weeks ago, # ^ |   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 getRHS = 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 casescase 1. $n >= 0, m >= 0$case 2. $n < 0, m >= 0$case 3. $n >= 0, m < 0$case 4. $n < 0, m < 0$
•  » » » 7 weeks ago, # ^ |   0 thanks, this helped me a lot XD