切比雪夫距离与曼哈顿距离
结论¶
- 曼哈顿坐标系是通过切比雪夫坐标系旋转 \(45^\circ\) 后，再缩小到原来的一半得到的。
- 将一个点 \((x,y)\) 的坐标变为 \((x + y, x - y)\) 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
- 将一个点 \((x,y)\) 的坐标变为 \((\dfrac{x + y}{2},\dfrac{x - y}{2})\) 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。
曼哈顿距离->切比雪夫距离¶
假设 \(A(x_1,y_1),B(x_2,y_2)\)，
我们把曼哈顿距离中的绝对值拆开，能够得到四个值，这四个值中的最大值是两个非负数之和，即曼哈顿距离。则 \(A,B\) 两点的曼哈顿距离为：
\[
\begin{aligned}
d(A,B)&=|x_1 - x_2| + |y_1 - y_2|\\
&=\max\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\end{Bmatrix}\\
&= \max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_1) - (x_2 - y_2)|)
\end{aligned}
\]
我们很容易发现，这就是 \((x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)\) 两点之间的切比雪夫距离。
所以将每一个点 \((x,y)\) 转化为 \((x + y, x - y)\)，新坐标系下的切比雪夫距离即为原坐标系下的曼哈顿距离。
切比雪夫距离->曼哈顿距离¶
同理，\(A,B\) 两点的切比雪夫距离为：
\[
\begin{aligned}
d(A,B)&=\max\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\end{Bmatrix}\\
&=\max\begin{Bmatrix} \left|\dfrac{x_1 + y_1}{2}-\dfrac{x_2 + y_2}{2}\right|+\left|\dfrac{x_1 - y_1}{2}-\dfrac{x_2 - y_2}{2}\right|\end{Bmatrix}
\end{aligned}
\]
而这就是 \((\dfrac{x_1 + y_1}{2},\dfrac{x_1 - y_1}{2}), (\dfrac{x_2 + y_2}{2},\dfrac{x_2 - y_2}{2})\) 两点之间的曼哈顿距离。
所以将每一个点 \((x,y)\) 转化为 \((\dfrac{x + y}{2},\dfrac{x - y}{2})\)，新坐标系下的曼哈顿距离即为原坐标系下的切比雪夫距离。