Manhattan Distance & Chebyshev distance
DarkMoon_Dragon · · 个人记录
Manhattan Distance & Chebyshev distance
曼哈顿距离 与 切比雪夫距离
1. 曼哈顿距离
定义
- 对于两个点
(x1,y1),(x2,y2) ，定义他们的曼哈顿距离为|x1−x2|+|y1−y2| ，即两点横纵坐标差之和。也是每次只能走四联通块，两点的最短距离。
性质
- 对于曼哈顿距离相同的点，他们分布在同一横纵截距大小相同的直线上。即图中每一个正方形边界上的整点到原点的曼哈顿距离相同。
- 三角不等式
d(i,j)≤d(i,k)+d(k,j) ，即从对象i 到对象j 的直接距离不会大于途经的任何其他对象k 的距离和 - 中位数定理 -> 到所有点距离之和最小
2. 切比雪夫距离
定义
- 对于两个点
(x1,y1),(x2,y2) ，定义他们的曼哈顿距离为max{|x1−x2|,|y1−y2|} ，即横纵坐标距离差的最大值。也是每次只能走八联通块，两点的最短距离。
性质
- 对于切比雪夫距离相同的点，他们分布在以原点为中心的正方形边界上。即图中每一个正方形边界上的整点到原点的曼哈顿距离相同。
- 平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。
- 如图
3. 两者的相互转化
曼哈顿距离转切比雪夫距离
- 将每一个点
(x,y) 转化为(x+y,x−y) ，新坐标系下的切比雪夫距离即为原坐标系下曼哈顿距离。- 证明可以讨论一下
x_1,x_2,y_1,y_2 - 实际上没有卵用。因为求切比雪夫距离是
\mathcal{O(n)} 的。
切比雪夫距离转曼哈顿距离
- 平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。
- 按照刚才的思路再还原回去。
- 将每一个点
(x,y) 转化为(\cfrac{x+y}{2},\cfrac{x-y}{2}) ，新坐标系下的曼哈顿距离即为原坐标系下切比雪夫距离。- 实际运用中此方法常用，曼哈顿距离一般可以通过排序前缀和的方式降低计算复杂度。
- 注意到除法如果向下取整可能会使答案不正确，所以考虑先不除以2，最后求完答案再除以2也是一样的，形象的理解可以说成，曼哈顿坐标系是通过切比雪夫坐标系旋转后，再缩小到原来的一半得到的。