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

First Post:

Last Update:

Word Count:
274

Read Time:
1 min

Page View: loading...

维空间下 ,则两点的曼哈顿距离为:

显然,若将这个空间中的任意一点 映射到 维空间中的 点,其中 点每一维的坐标为

这里 枚举 的所有子集。

容易注意到, 时,变换是特别的,具体来说,这恰好是 的两个根。

然而, 时的变换是平凡的,因为这时两种距离没有区别。

我们考虑 时的变换,若把二维平面上每一点 变换到 ,则前者的曼哈顿距离即为后者的切比雪夫距离。

同时,我们还注意到,这时变换是可逆的,具体来说,若将二维平面上每一点 变换到 ,则前者的切比雪夫距离即为后者的曼哈顿距离。

遗憾的是,在更高维的空间,曼哈顿距离到切比雪夫距离的变换是不可逆的。

如果我们直接尝试变换切比雪夫距离到曼哈顿距离呢?

在二维,有

因此

但是,在更高维度,很难找到类似的形式。