计算几何学习笔记 [基础 II]

距离

欧几里得距离

欧氏距离，也是我们一般使用的距离。

我们熟悉的是：

若平面里有点 \(A(x_1,y_1),B(x_2,y_2)\)，那么它们之间的欧氏距离 \(d(A,B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)；

若空间里有点 \(A(x_1,y_1,z_1),B(x_2,y_2,z_2)\)，那么它们之间的欧氏距离是 \(d(A,B) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}\)。

我们大胆猜想一下：\(n\) 维空间的欧氏距离公式？

若 \(A(x_1,x_2,\cdots,x_n),B(y_1,y_2,\cdots,y_n)\)，那么 \(d(A,B) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \cdots + (x_n - y_n)^2}\)。

曼哈顿距离

传说中，曼哈顿距离的得名是因为它很 方。以至于在计算距离的时候就自然而然有一种完全不同的计算方式：只考虑横着走，竖着走。根本不会像欧氏距离一样斜着走，因为会撞墙（笑

稍微考据了一下，好像确实是这样的：

曼哈顿的街道有大道（Avenue）和街（Street）两种命名方式，大道通常为南北向，街通则常为东西向。

之后我又翻找到了一张曼哈顿的地图：

这个大概是曼哈顿的分区。

我们随意看其中几个吧：

Beekman

Chinatown

哇！还真的是很方。

回到正题。在二维空间内，两个点之间的曼哈顿距离就是它们横坐标之差的绝对值与纵坐标之差的绝对值之和。

设 \(A(x_1,y_1),B(x_2,y_2)\)，那么曼哈顿距离 \(d(A,B) = |x_1 - x_2| + |y_1 - y_2|\)。

同样的，推广到 \(n\) 维空间：

设 \(A(x_1,x_2,\cdots,x_n),B(y_1,y_2,\cdots,y_n)\)，那么曼哈顿距离：\(d(A,B) = |x_1 - y_1| + |x_2 - y_2| + \cdots + |x_n - y_n|\)。

曼哈顿距离还有一些性质，都是简单易懂的：

1. 非负性：曼哈顿距离是一个非负数。
2. 统一性：点到自身的曼哈顿距离为 \(0\)。
3. 对称性：\(A\) 到 \(B\) 与 \(B\) 到 \(A\) 的曼哈顿距离相等，且是对称函数。\(d(A,B) = d(B,A)\)。
4. 三角不等式：从点 \(i\) 到 \(j\) 的直接距离不会大于途经的任何其它点 \(k\) 的距离。\(d(i,j) \le d(i,k) + d(k,j)\)。

切比雪夫距离

这个名字好像很熟悉？我们好像有个“切比雪夫不等式”？

回到正题。“切比雪夫距离”是指坐标差的绝对值的最大值。

比如二维空间，点 \(A(x_1,y_1),B(x_2,y_2)\)，有切比雪夫距离：\(d(A,B) = \max(|x_1 - x_2|,|y_1 - y_2|)\)。

仍然推广到 \(n\) 维。点 \(A(x_1,x_2,\cdots,x_n),B(y_1,y_2,\cdots,y_n)\)，切比雪夫距离：\(d(A,B) = \max\{|x_1 - y_1|, |x_2 - y_2|, \cdots, |x_n - y_n|\}\)。

曼哈顿距离和切比雪夫距离的转化

考虑画出平面内，到原点的曼哈顿距离为 \(1\) 的所有点，以及到原点切比雪夫距离为 \(1\) 的所有点：

这两个东西画出来是相似的。有什么联系呢？

考虑 \(A(x_1,y_1)\) 和 \(B(x_2,y_2)\) 的曼哈顿距离拆开：

\[\begin{aligned} d(A,B) & = |x_1 - x_2| + |y_1 - y_2| \\ & = \max\{x_1 - x_2 + y_1 - y_2,x_1 - x_2 + y_2 - y_1, \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_2 - x_1 + y_1 - y_2,x_2 - x_1 + y_2 - y_1\} \\ & = \max(|(x_1 + y_1) - (x_2 + y_2)| , |(x_1 - y_1) - (x_2 - y_2)|) \end{aligned} \]

也就是 \((x_1 + y_1,x_1 - y_1),(x_2 + y_2,x_2 - y_2)\) 的切比雪夫距离！

所以将每一个点 \((x,y)\) 转化为 \((x + y,x - y)\)，新坐标系下的切比雪夫距离即为原坐标系下的曼哈顿距离。

同理，\(A(x_1,y_1),B(x_2,y_2)\) 的切比雪夫距离：

\[\begin{aligned} d(A,B) & = \max(|x_1 - x_2|, |y_1 - y_2|) \\ & = \max \left\{ \left| \dfrac{x_1 + y_1}{2} - \dfrac{x_2 + y_2}{2} \right| + \left| \dfrac{x_1 - y_1}{2} - \dfrac{x_2 - y_2}{2} \right| \right\} \end{aligned} \]

也就是 \((\dfrac{x_1 + y_1}{2},\dfrac{x_1 - y_1}{2}),(\dfrac{x_2 + y_2}{2},\dfrac{x_2 - y_2}{2})\) 两点间的曼哈顿距离。

所以把每一个点 \((x,y)\) 转化为 \((\dfrac{x + y}{2},\dfrac{x - y}{2})\)，新坐标系下的曼哈顿距离即为原坐标系下的切比雪夫距离。

\(L_m\) 距离

曼哈顿距离和欧氏距离都可以看做是 \(L_m\) 距离的一种情况。

一般地，规定平面上两点的 \(L_m\) 距离：

\[d(L_m) = (|x_1 - x_2|^m + |y_1 - y_2|^m)^{\frac{1}{m}} \]

\(L_1\) 距离是曼哈顿距离，\(L_2\) 距离是欧氏距离。

我们总有一种直觉，曼哈顿距离和欧氏距离从某种角度上是一致的。提取这个一致的形式，加以归纳，就得到 \(L_m\) 距离。

当 \(m\) 更大的时候，这个式子可能就没有了很直观的意义？（至少我暂时不太知道）

Pick 定理

给定顶点均为整点的简单多边形，其面积 \(A\) 和内部格点数目 \(i\)、边上格点数目 \(b\) 的关系：\(A = i + \dfrac{b}{2} - 1\)。

随手画了几个情况，可以辅助学习一下：

Pick 定理还有一些推论：

1. 取格点的组成图形的面积为一单位。
   • 在平行四边形格点，皮克定理依然成立。
   • 套用于任意三角形格点，皮克定理则是 \(A = 2i + b - 2\)。

原因很简单。取平行四边形为单位面积就相当于把原来正方形的格点图整个拉伸了一下，实质没变；而既然平行四边形上它成立，把每个平行四边形剖分为两个三角形，那么对于三角形网格也成立，只不过面积翻倍而已。