Trjtdtk

This is from a Kickstart problem:

Note: The Manhattan distance between two squares (r1,c1) and (r2,c2)
is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the
absolute value.

Then in the analysis:

Note that the manhattan distance has an equivalent formula:

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

This formula is based on the fact that for any point, the set of
points within a manhattan distance of K form a square rotated by 45
degrees. The benefit of this formula is that if we fix (x2, y2), the
distance will be maximized when x1 + y1 and x1 - y1 are either
maximized or minimized.

Could someone explain in more details how this formula can be derived?

Lemma. $|a|+|b|=max(|a+b|, |a-b|)$ for any real number $a$ and $b$.

Proof 1.
$|x|=max(x, -x)$ for all real number $x$. So
$$beginaligned
|a|+|b|
&=max(a, -a) + max(b, -b)\
&=max(a+b, a-b, -a+b, -a-b)\
&=max(max(a+b, -a-b), max(a-b, -(a-b))\
&=max(|a+b|, |a-b|)
endaligned$$

Proof 2.
There are $2 times 2 = 4$ cases.

• 
  $age 0$
  
  
  • 
    $bgt 0$. LHS is $a+b$, RHS is $a+b$.
  
  
  • 
    $ble 0$. LHS is $a-b$, RHS is $a-b$.
  
  


• 
  $alt 0$
  
  
  • 
    $bgt 0$. LHS is $-a+b$, RHS is $-(a-b)$.
  
  
  • 
    $ble 0$. LHS is $-a-b$, RHS is $-(a+b)$.
  
  

One dimensionality of Manhattan-distance.

The Manhattan-distance of two points $(x_1, y_1)$ and $(x_2, y_2)$ is either $|(x_1+y_1)-(x_2+y_2)|$ or $|(x_1-y_1)-(x_2-y_2)|$, whichever is larger. That is, $ d((x_1, y_1),(x_2, y_2))= max(|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|)$$

Proof: By definition,
$$d((x_1, y_1),(x_2, y_2))=|x_1-x_2| + |y_1-y_2|.$$
Now apply the lemma above. QED.

_{This answer also serves as a complement to another answer of mine.}