曼哈顿与切比雪夫距离

定义

1. 切比雪夫距离： $\max{|x_i-x_j|,|y_i-y_j|}$

直观感受一下，它描述两个位置最大的差量。

1. 曼哈顿距离：$|x_i-x_j|+|y_i-y_j|$

直观感受一下，它描述两个位置的垂直距离。

转化

考虑建立直角坐标系。

到原点切比雪夫距离为 $1$ 的点构成一个平行于坐标轴的正方形。

而曼哈顿距离为 $1$ 的点构成了一个斜 $45\degree$ 放置的正方形。

考虑将切比雪夫距离为 $(x,y)$ 的点绕原点旋转 $45\degree$ 然后缩小，即可得到对应的曼哈顿距离。

具体地，考虑

$$\begin{bmatrix} \hat i\\ \hat j \end{bmatrix} \to \begin{bmatrix} \hat i + \hat j\over 2\\ \hat i - \hat j\over 2 \end{bmatrix}$$

同理，我们有

$$\begin{bmatrix} \hat i\\ \hat j \end{bmatrix} \to \begin{bmatrix} \hat i + \hat j\\ \hat i - \hat j \end{bmatrix}$$

没了