曼哈顿距离与切比雪夫距离及其相互转化

本文只讨论二维空间中的曼哈顿距离与切比雪夫距离

曼哈顿距离

定义

设平面空间内存在两点，它们的坐标为(x1,y1)，(x2,y2)

则dis=|x1-x2|+|y1-y2|

即两点横纵坐标差之和

煮个栗子

如图所示，图中A,B两点的曼哈顿距离为AC+BC=4+3=7

切比雪夫距离

定义

设平面空间内存在两点，它们的坐标为(x1,y1)，(x2,y2)

则dis=max(|x1-x2|,|y1-y2|)

即两点横纵坐标差的最大值

再煮个栗子

dis=max(AC,BC)=AC=4

两者之间的关系

两者的定义看上去好像毛线关系都没有，但实际上，这两种距离可以相互转化！

我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)

如果用曼哈顿距离表示，则与原点距离为1的点会构成一个边长为1的正方形

如果用切比雪夫距离表示，则与原点距离为1的点会构成一个边长为2的正方形

仔细对比这两个图形，你会发现什么？

没错！

第二个图像是由第一个图像放大两倍后旋转45^{\circ}得到的

然后根据向量矩阵什么乱七八糟的可以得到

第一个图中的点(x,y)对应第二个图中的点(\dfrac{x+y}{2},\dfrac{x-y}{2})

这样我们就可以将其进行互相转换了