6.5 对偶
(Duality)

人们可能很难想到，排列对于像 6.1 节中的第4项这样的平面点集问题那么有用。这一应用以及排列许多其他应用的关键在于一个被称为对偶(duality)的重要概念。其基本思想是，直线可以由两个数字确定，所以直线可以与坐标为这两个数字的点(point)相关联。这好像跟射影空间中的点、直线的对偶关系一样。例如，由 $y = mx + b$ 确定的直线可以与点 $(m, b)$ 相关联。通常，这些点所在的空间被称为参数空间(parameter space)，因为点的坐标就是直线的参数。由于原始空间和参数空间都是等价的二维空间，习惯上将它们视为一个单一的空间，只是坐标有两种解释，这确实容易让人感到困惑。既然从直线可以映射到到点，就可以反过来，把平面上的任何点的坐标解释成斜率和截距时，都可以将之视为一条直线。这些映射共同确定了点与直线之间的对偶关系: 每一条直线都与一个唯一的点相关联，每一个点也与一条唯一的直线相关联。

有很多种不同的点-线对偶映射关系，这取决于直线方程怎么写。在特定的上下文中，每种映射都有其优缺点。我们已经提到了映射 $L: y = mx + b \Leftrightarrow p: (m, b)$，它的优势在于利用了我们所熟悉的对斜率和截距的概念。映射 $L: ax + by = 1 \Leftrightarrow p: (a, b)$ 定义了所谓的极对偶(polar duality)(Coxeter & Greitzer 1967)。这种映射具有优秀的几何性质，我们将在练习中探讨一些(练习 6.5.3[3] 和 [4])。但是，在本章中我们将全部使用如下的映射:

$$ \begin{equation}\label{f6.1} L: y = 2ax - b \Leftrightarrow p: (a, b) \end{equation}\tag{6.1} $$

我们使用符号 $\mathbb{D}$ 来表示此映射: $\mathbb{D}(L) = p$ 且 $\mathbb{D}(p) = L$。这看起来可能是一个奇怪的映射选择，但它在计算几何中通常是最方便的，这主要是因为它与抛物面变换(第 5.7.2 节)有着密切的联系。我们先以一种非形式化的方式感受一下这种联系，再通过一系列引理(第 6.5.2 节)进行深入考察它。

6.5.1. 对偶映射

点 $p = (a, b)$ 与直线 $L: y = 2ax - b$ 之间的关系并非显而易见的。但是，$L$ 与5.8.1 节中的公式(5.12)的相似性，表明它应当与抛物线 $y = x^2$ 存在关联。回想一下，$y = 2ax - a^2$ 是该抛物线在点 $(a, a^2)$ 处的切线。因此，$\mathbb{D}(p)$ 将满足 $b = a^2$ 的点 $p = (a, b)$映射到这条切线上。如果 $b < a^2$，那么 $\mathbb{D}(p)$ 映射到一条平行于该切线但在垂直方向上抬高了 $(a^2 - b)$ 的直线上，正如我们在图 5.23 中看到那样。如果 $b > a^2$，那么 $\mathbb{D}(p)$ 映射到一条位于该切线下方 $(b - a^2)$ 处的平行直线。图 6.6 展示了 $a = 2$ 且 $b \in \{0, 4, 8\}$ 的三个点的情况。在此及全文中，我们将点及其对偶表达在同一个空间内。

利用这种对偶变换，我们可以将任意点集转换为直线排列，反之亦然。这之所以非常有用，是因为点之间的关系在其对偶的直线排列中，往往能更明确地揭示出来。图 6.7 展示了图 6.1 中所示十条直线及其对偶点，而图 6.8 则单独显示了这些点。这个例子将在后面的6.7.6 节中使用。

6.5.2. 对偶特性

在本节中，我们将推导对偶变换的一些基本性质，这些性质将在后续章节中使用。

引理 6.5.1. $\mathbb{D}$ 是其自身的逆: $\mathbb{D}(\mathbb{D}(x)) = x$，其中 $x$ 既可以是点也可以是直线。

证明: 该映射被定义为对称的。 □

引理 6.5.2. $\mathbb{D}$ 是所有非垂直直线与平面上所有点之间的一一映射。

证明: 垂直直线不能表示为 $y = 2ax - b$ 的形式，并且这些是唯一不能这样表示的直线。□

涉及垂直直线这种特殊情况，在任何给定问题中，都可以通过稍微旋转直线，使得没有直线是垂直的，来回避它。我们将简单地把垂直直线排除在考虑之外。对偶变换保持点线的关联：

引理 6.5.3. 当且仅当点 $p$ 在直线 $L$ 上，有点 $\mathbb{D}(L)$ 在直线 $\mathbb{D}(p)$ 上，。

证明: 设 $L$ 为直线 $y = 2ax - b$ 以及 $p = (c, d)$。如果 $p$ 在 $L$ 上，有 $d = 2ac - b$。 $\mathbb{D}(L)$ 是 $(a, b)$，而 $\mathbb{D}(p)$ 是直线 $y = 2cx - d$。将 $\mathbb{D}(L)$ 的坐标代入 $\mathbb{D}(p)$ 的方程得到 $b = 2ca - d$，这是成立的，因为这只是 $d = 2ac - b$ 的重新排列。因此 $\mathbb{D}(L)$ 在 $\mathbb{D}(p)$ 上。反向蕴含关系可由引理 6.5.1 得出。□

两点确定一条直线，其对偶形式为，两条直线确定一个交点:

引理 6.5.4. 直线 $L_1$ 和 $L_2$ 相交于点 $p$ 当且仅当直线 $\mathbb{D}(p)$ 经过两点 $\mathbb{D}(L_1)$ 和 $\mathbb{D}(L_2)$。

证明: 这可以通过两次应用引理 6.5.3 得出。因为 $p$ 位于 $L_1$ 和 $L_2$ 上，所以 $\mathbb{D}(L_1)$ 和 $\mathbb{D}(L_2)$ 都位于 $\mathbb{D}(p)$ 上。同样，反向蕴含关系由引理 6.5.1 得出。□

当排除垂直线时，点和直线可以如上所述明确地表示为"上方(above)", "之上(on)"或"下方(below)"。对偶映射在以下意义上可以被看作反转了垂直顺序:

引理 6.5.5. 如果点 $p$ 位于直线 $L$ 上方，则直线 $\mathbb{D}(p)$ 位于点 $\mathbb{D}(L)$ 下方。对称地，如果 $p$ 位于 $L$ 下方，则 $\mathbb{D}(p)$ 位于 $\mathbb{D}(L)$ 上方。

证明: 我们只证明第一个命题。假设 $p$ 位于 $L$ 上方。直线 $L$ 为 $y = 2ax - b$，并且 $p = (c, d)$。因为 $p$ 位于 $L$ 上方，所以 $p$ 的 $y$ 坐标大于 $L$ 在 $x = c$ 处的取值，即，$d > 2ac - b$。 $\mathbb{D}(p)$ 是直线 $y = 2cx - d$，且 $\mathbb{D}(L) = (a, b)$。将 $x = a$ 代入 $\mathbb{D}(p)$ 得到 $y$ 坐标为 $2ca - d$，该值小于 $b$，因为 $b > 2ca - d$ 只是 $d > 2ac - b$ 的重新排列。因此，直线 $\mathbb{D}(p)$ 位于点 $\mathbb{D}(L)$ 下方。□

这点可以在图 6.6 中清楚看到。例如，点 $c$ 在直线 $B$ 上方，而直线 $C$ 在点 $b$ 下方。

6.5.3. 练习

[easy] 共线点 Collinear points。$k$ 个共线点的对偶 $\mathbb{D}$ 是什么?
正多边形的对偶 Dual of regular polygons。找出以原点为中心的正多边形的顶点和边的对偶 $\mathbb{D}$，该多边形的方向设定为没有边是垂直的。 提示: 通过研究以原点为中心的单位圆，分析当顶点数 $n \to \infty$ 时会发生什么。
极对偶性质 Polar dual properties。回想一下，极对偶是由映射 $L : ax + by = 1 \iff p : (a, b)$ 定义的。
1. 从几何上将极对偶点和直线与以原点为中心的单位圆联系起来。
2. 证明与单位圆相交于点 $a$ 和 $b$ 的直线的极对偶是点 $p$，该点 $p$ 是圆在 $a$ 和 $b$ 处的切线的交点。
正多边形的极对偶 Polar dual of regular polygons。在极对偶下重做练习2，找出以原点为中心的正多边形的顶点，以及包含其边的直线的极对偶。
半平面的交集 Intersection of halfplanes。
1. 设 $H$ 是一组 $n$ 个半平面，每个半平面都包含负 $y$ 轴的一部分，即，它们都朝下。令 $Q = \cap H$，即所有半平面的交集。 $S$ 为 $\mathbb{D}(H)$，即，界定这些半平面的直线的对偶点集。最后，设 $P = \mathcal{H}(S)$，即 $S$ 的凸包。解释 $P$ 和 $Q$ 的结构之间的关系。
2. 根据你的观察，提出一种计算半平面交集的算法。

6.5 对偶(Duality)

6.5.1. 对偶映射

6.5.2. 对偶特性

6.5.3. 练习

6.5 对偶
(Duality)