Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Manhattan distance trick in higher dimensions

Revision en2, by kaldiuo, 2018-02-04 16:26:29

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kaldiuo 2018-02-04 16:26:29 35 Tiny change: ', |y1-y2|). Can thi' -> ', |y1-y2|) (also known as Chebyshev distance). Can thi'
en1 English kaldiuo 2018-02-04 13:51:47 335 Initial revision (published)