曼哈顿距离与切比雪夫距离

发表于

切比雪夫距离定义:

对于平面上的两个点 a,ba,b,它们的切比雪夫距离为 max⁡(∣xa−xb∣,∣ya−yb∣)\max(|x_a-x_b|, |y_a-y_b|)

即两个点水平距离和竖直距离的较大值, 也可以看成两个点在八个方向的走法中的距离.

曼哈顿距离定义:

对于平面上的两个点 a,ba,b,它们的切比雪夫距离为 ∣xa−xb∣+∣ya−yb∣|x_a-x_b|+|y_a-y_b|

即两个点水平距离和竖直距离的和, 也可以看成两个点在四个方向的走法中的距离.

这两种距离是可以相互转化的.

切比雪夫距离转曼哈顿距离

转化公式: (x,y)−>(x+y2,x−y2)(x, y) -> (\frac{x+y}{2},\frac{x-y}{2})

证明:

考虑距离 (0,0)(0, 0) 的切比雪夫距离为 CC 的点，它们构成了一个这样的正方形

1
2
3
4
5
6
7
8
9
10
....|.....
.#######..
.#..|..#..
.#..|..#..
-#-----#--
.#..|..#..
.#..|..#..
.#######..
....|.....
....|.....

而距离 (0,0)(0, 0) 的曼哈顿距离为 CC 的点，容易想象到其实就是这个正方形旋转 4545 度， 然后缩小到原来的 12\frac{1}{\sqrt{2}}

那么对于原正方形上的点 (x,y)(x, y) 旋转 4545 度后变为 (x×cosπ4+x×sinπ4,x×cosπ4−x×sinπ4)(x\times cos\frac{\pi}{4} + x\times sin\frac{\pi}{4}, x\times cos\frac{\pi}{4} - x\times sin\frac{\pi}{4})

再乘上 12\frac{1}{\sqrt{2}} , 变成 (12(x×cosπ4+x×sinπ4),12(x×cosπ4−x×sinπ4))(\frac{1}{\sqrt{2}}(x\times cos\frac{\pi}{4} + x\times sin\frac{\pi}{4}),\frac{1}{\sqrt{2}} (x\times cos\frac{\pi}{4} - x\times sin\frac{\pi}{4})) 即 (x+y2,x−y2)(\frac{x+y}{2}, \frac{x-y}{2})

这样新坐标系中两点的曼哈顿距离就是原坐标系中的切比雪夫距离

曼哈顿距离转切比雪夫距离

公式 : (x,y)−>(x+y,x−y)(x, y) -> (x + y, x - y)

证明同理.

既然要把它们相互转化，所以它们一定有各自擅长解决的问题

切比雪夫距离擅长解决的问题:

  1. 两个点的某种距离小于某个值. (限制条件)
  2. 横纵距离在求最值的情况下相互影响不大.
  3. …

曼哈顿距离擅长解决的问题:

  1. 两个点某种距离最小 (答案要求) 如平面最近点对。
  2. 横纵距离在求和的情况下相互影响不大.
  3. …

例题:

S2OJ随机

USACO Cow Neighborhoods G

[TJOI2013]松鼠聚会