由p范数诱导的距离，当p趋于无穷时为切比雪夫距离

摘要: 切比雪夫距离与闵可夫斯基距离的关系

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

此前我们解决过很多几何问题。这些几何问题都是在欧式空间的框架下的。在文章 几何题汇总 中我们总结了几何问题相关的分类题目清单。更多相关的题解和代码模板可以在公众号置顶标签或下方菜单的几何标签中查看，下面是部分文章：

算法与代码模板：

• 【模板】二维向量的实现
• 点
• 极角
• 直线和线段
• 一点绕另一点旋转
• 凸包
• 凸包的直径，旋转卡尺算法
• 多边形
• 半平面交
• 扫描线算法(Line-Sweep)
• 射线旋转扫描线算法(Angular-Sweep)

题解：

• 【多维分桶】最小面积矩形
• 曼哈顿距离
• 【多维分桶】N 个点中最多有多少点共线
• 【分类讨论】力扣335-路径交叉
• 力扣LCP37-最小矩形面积

欧式空间是有限维的实内积空间，内积空间是定义了内积的线性空间，由于内积可以诱导出范数，范数进一步可以诱导出距离，因此欧式空间自然也是赋范线性空间和度量空间。

有的时候会遇到一些问题，描述上跟经典的几何问题一样，只是对距离的定义变了，比如两个点之间的距离定义为曼哈顿距离。下面就是一个题目：

这看似很小的改变可能会使得以前的算法就完全不适用了，本文我们先来看一些理论上的东西，后续的文章中我们再解决本题。

曼哈顿距离是由 p 范数诱导的距离当 $p=1$ 的情况，我们熟悉的欧氏距离是 $p=2$ 的情况。由于 1 范数无法从内积诱导出来（事实上可以证明，p范数只有当 $p=2$ 时才能从内积诱导出来），因此虽然曼哈顿距离可以构成度量空间，但无法定义内积，自然就无法构成内积空间，那么我们在欧式空间中解决的几何问题，凡是在算法中用到角度，投影等概念的算法均不能套用在曼哈顿距离下。

上面的题目中，如果距离定义是欧氏距离，这就是一个求点集的直径的问题，主流的算法为旋转卡尺算法，参考文章 凸包的直径，旋转卡尺算法，该算法的过程是依赖旋转，垂直等概念的，而这种跟角度相关的概念是依赖内积的，而曼哈顿距离无法定义内积，那自然就无法套用这种跟角度相关的算法，需要另找解决方案。

在常见的距离定义中，还有一种称为切比雪夫距离，曼哈顿距离于切比雪夫距离可以互相转化，这种转化在一些曼哈顿距离定义的几何问题中非常有力，当然也可以解决上面这道题。

本文我们先将几种常见的距离的定义罗列一下，然后论证一下 p 范数诱导的距离当 p 趋于无穷的时候为切比雪夫距离这件事。后续我们再通过将曼哈顿距离转化为切比雪夫距离来解决上面这道题。

曼哈顿距离

曼哈顿距离是 19 世纪由闵可夫斯基提出的，定义为两个点在标准坐标系上的绝对轴距总和。由于曼哈顿的道路都是方方正正的，因此得名。

$$\rho(\mathbf{x}, \mathbf{y}) = \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}| , \quad\quad \forall \mathbf{x}, \mathbf{y} \in X$$

曼哈顿距离在数据科学中很常见，计算简单快速，可解释性强，但也有一些缺点，比如如果数据分布不均匀，可能受到异常值影响等等。

切比雪夫距离

切比雪夫距离也是一种在数学和数据科学中常用的距离，定义为两个点在标准坐标系上的绝对轴距的最大值：

$$\rho(\mathbf{x}, \mathbf{y}) = \max\limits_{1 \leq i\leq n} |x_{i} - y_{i}| , \quad\quad \forall \mathbf{x}, \mathbf{y} \in X$$

由于仅考虑最大的坐标差，所以切比雪夫距离对异常值的鲁棒性更好一些。

p范数诱导的距离

如果集合 $X$ 上定义了范数 $\Vert x\Vert, \forall x\in X$，那么 $X$ 是一个赋范空间。距离可以由范数来诱导：

$$\rho(x, y) = \Vert x - y\Vert, \forall x,y \in X$$

也就是说，给定了一个赋范空间，自然就隐含了它是一个度量空间。

比如 p 范数是一种常见的范数，其定义如下：

$$\Vert x\Vert_{p} = \left( \sum\limits_{i=1}\limits^{n} |x_{i}|^{p} \right)^{1/p} , \quad\quad \forall x \in X$$

于是 p 范数诱导的距离定义如下：

$$\rho(\mathbf{x}, \mathbf{y}) = \left( \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \right)^{1/p} , \quad\quad \forall \mathbf{x}, \mathbf{y} \in X$$

这种距离也称为闵可夫斯基距离。当 $p=1$ 时，p 范数诱导的距离正是曼哈顿距离，$p=2$ 时即为欧氏距离。

p趋于无穷的情况

在 p 范数中，当 $p \rightarrow\infty$ 时，其诱导出的距离，也就是 $\infty$ 范数距离，正是切比雪夫距离，也就是：

$$\lim\limits_{p\rightarrow +\infty} \left( \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \right)^{1/p} = \max\limits_{1 \leq i\leq n} |x_{i} - y_{i}|$$

这件事不是那么显然，下面我们来证明一下。

证明

假设 $f(p) = \left( \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \right)^{1/p}$，取对数后得到：

$$\ln f(p) = \frac{1}{p} \ln\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p}$$

记 $g(p) = \ln\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p}$，$h(p) = p$。这里 $g(p)$ 由 $n$ 个指数函数的和组成，因此是连续的；$h(p) = p$ 显然也是连续的，

另一方面，由指数函数的性质有$\lim\limits_{p\rightarrow +\infty}g(p) = +\infty$，$\lim\limits_{p\rightarrow +\infty}h(p) = +\infty$。因此可以对 $\ln f(p) = \frac{g(p)}{h(p)}$ 用洛必达法则，有：

$$\lim\limits_{p\rightarrow +\infty}\ln f(p) = \lim\limits_{p\rightarrow +\infty} \frac{g(p)}{h(p)} = \lim\limits_{p\rightarrow +\infty} \frac{g'(p)}{h'(p)} = \lim\limits_{p\rightarrow +\infty}g'(p)$$

对 $g’(p)$ 用复合函数求导法则 $f(g(x))’ = f’(g(x))g’(x)$，以及指数函数的导数 $a^{x} = a^{x}\ln a$，有：

$$g'(p) = \frac{\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p}\ln|x_{i}-y_{i}|}{\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p}}$$

令 $\max\limits_{1\leq i \leq n}|x_{i} - y_{i}| = |x_{k} - y_{k}|$，则上式可变形为：

$$\begin{align} g'(p) &= \frac{\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p}\ln|x_{i}-y_{i}|}{\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p}} \\ &= \frac{\sum\limits_{i=1}\limits^{n} |\frac{x_{i} - y_{i}}{x_{k} - y_{k}}|^{p}\ln|x_{i}-y_{i}|}{\sum\limits_{i=1}\limits^{n} |\frac{x_{i} - y_{i}}{x_{k} - y_{k}}|^{p}} \\ \end{align}$$

上式分母的和式中的 $n$ 项，均为指数函数 $a^{p}$ 的形式。假设其中有 $m$ 项是 $a=1$（$m\geq 1$），即$|x_{i}-y_{i}|$取到最大值 $|x_{k}-y_{k}|$ 的那些项，当 $p\rightarrow +\infty$ 时为 1；剩下的 $n-m$项都是 $a\in [0, 1)$ 的情况。当 $p\rightarrow +\infty$ 时为 0。

类似地，上式分子的和式也是 $n$ 项，均为指数函数乘以一个常数 $a^{p}c$ 的形式，其中 $c=|x_{i}-y_{i}|$。同样地有 $m$ 项是 $a=1$ 的情况，这种情况下 $p\rightarrow +\infty$ 的结果就是 $|x_{k}-y_{k}|$，剩下的 $n-m$ 项是 $a\in [0, 1)$ 的情况。当 $p\rightarrow +\infty$ 时依然为 0。

综上，$\lim\limits_{p\rightarrow +\infty}g’(p)$ 的结果为：

$$\lim\limits_{p\rightarrow +\infty}g'(p) = \frac{m\ln|x_{k} - y_{k}|}{m} = \ln|x_{k} - y_{k}|$$

也就是 $\lim\limits_{p\rightarrow +\infty}\ln f(p) = \ln|x_{k} - y_{k}|$，于是最终得到 $\lim\limits_{p\rightarrow +\infty}f(p) = |x_{k} - y_{k}|$，即：

$$\lim\limits_{p\rightarrow +\infty}\left( \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \right)^{1/p} = \max\limits_{1\leq i \leq n}|x_{i} - y_{i}|$$

$\Box$

总结

本文我们讨论了在欧氏距离定义下的计算几何问题，当距离改为其它定义时，算法可能不再适用的问题。然后给出了几种在数据科学中常见的几个距离定义，它们都可以在 $p$ 范数诱导出来。

之后我们重点讨论了 $p$ 范数当 $p\rightarrow +\infty$ 时，诱导出的距离是切比雪夫距离这件事，证明过程用到了微积分中的多个经典结论，包括洛必达法则，复合函数求导，指数函数的导数和极限，只要大学或考研微积分的基础即可看懂，但是结论并不显然，值得看一下。

本文我们清楚了曼哈顿距离和切比雪夫距离的定义，以及它们在 p 范数框架下是什么关系。后续的文章中我们讨论这两个距离之间的互相转化，并基于这种转化解决一个在距离定义为曼哈顿距离下的计算几何问题。

---