6.7 应用
(Applications)

6.7.1. \(k\)-最近邻 (\(k\)-Nearest Neighbors)

维诺图可用于查找目标点的最近邻(5.1节和5.5.1节)， \(k\)阶维诺图可用于查找查询点的 \(k\) 个最近邻。这被用于所谓的"\(k\)-最近邻决策规则"。根据\(k\)个最近邻中占比最高的类别来对未知对象进行分类。 \(k\)-近邻在设施选址、信息检索和曲面插值方面也很有用。更多内容参见 Okabe, et al.(1992)。

6.7.2. 消除隐藏面 (Hidden Surface Removal)

如今，恐怕没有哪种几何计算比消除隐藏面使用的更频繁了，因为它是所有三维计算机图形学的基础，而三维计算机图形学又是许多电视广告和电影特效的基础。 这项任务是将三维空间中一组平坦、不透明、彩色的多边形，转化为从特定视点观察到的图像或"场景(scene)"。通常，这些多边形连接成一个表面，表面被遮挡的部分是"隐藏的"，必须从最终场景中"消除"。

设 \(n\) 为输入多边形的顶点总数，那么输出场景的复杂度可能是 \(\Omega(n^2)\)。如图 6.13 所示，水平矩形遮挡了垂直矩形的网格场景，其顶点数就 \(> \frac{1}{16}n^2\)。 如果我们要求输出一个多边形列表(图中的每个方形孔都需要填充)，那么在最坏情况下，没有任何算法能优于平方时间。 许多算法通过在某个环节引入一个 \(O(n \log n)\) 的排序步骤(Sutherland, Sproull & Shumacker 1974)，达到了 \(O(n^2 \log n)\) 的时间复杂度， 这仅比最优时间慢 \(O(\log n)\)。多年来，人们始终没有找到一个最优算法。直到排列(arrangements)理论的出现，带来了一个最坏情况下的最优 \(O(n^2)\) 算法(由 McKenna (1987) 提出)。 下面我将对此进行简述。

首先，假设空间中的多边形互相不能穿透，即它们内部是不相交的，但可能共享边界点。其次，假设点距离多边形无限远，使得所有视线都是平行的，这样我们就不必处理复杂的透视效果了。 事实上，任何具有有限视点的场景，都可以转换为视点在无限远处的场景，因此这并不失一般性。设视点位于 \((0, 0, +\infty)\)，\(xy\) 平面就是"视平面(viewplane)"，\(z = 0\)。 为了方便起见，可以在所有其他多边形下方添加一个巨大的多边形当背景，以确保所有视线都能击中某个多边形。

第一步，通过丢弃端点的 \(z\) 坐标，将多边形的每条边投影到 \(xy\) 平面上。这被称为正交投影。 接下来，将每条边延伸为其所在的整条直线。这在 \(xy\) 平面上形成了一个由 \(n\) 条直线组成的排列 \(\mathcal{A}\)， 根据定理 6.3.1，可以在 \(O(n^2)\) 时间内完成该排列的构建。 现在的任务是针对 \(\mathcal{A}\) 的每个单元，判定投影其中的空间多边形中，哪一个是最高的，也就是哪一个离视点最近。 然后，就可以根据多边形的颜色(如果需要阴影的话，还要参考其朝向)绘制这些单元。请注意，每个单元都有一个唯一的最前方多边形。

暴力算法将需要 \(O(n^3)\) 的时间，对于 \(O(n^2)\) 个单元中的每一个，计算 \(O(n)\) 个多边形的高度。挑战在于如何使每个单元仅花费常数时间。

McKenna 的算法采用了排列的拓扑扫描(topological sweep)，这是对 Edelsbrunner & Guibas(1989) 引入的平面扫描(2.4 节)的推广。 他不是用一条垂直线扫描排列，而是扫描一条垂直的"伪线(pseudoline)" \(L\)，这是一条与 \(\mathcal{A}\) 的每条线恰好相交一次的曲线，在交点处它都是从下到上穿过该线。 假设扫描线可以弯曲的优势在于，不再需要花费 \(O(\log n)\) 的时间在优先队列中查找以确定下一个被扫描的顶点。相反，可以维护一组无序的"可扫描(sweepable)"顶点。 即那些 \(L\) 穿过的相邻的两条边的顶点。在图 6.14 中，顶点 \(v\) 是可扫描的，因为被 \(L\) 穿过的单元 \(C\) 的两条边与它相关联。

除了固定的排列外，算法维护的数据结构包括被 \(L\) 穿过，而激活(active)的单元和边的列表，如图中的阴影单元。 对于每个激活单元 \(C\)，还要维护其在 \(xy\) 平面上的投影所覆盖 \(C\) 的所有多边形的列表，按 \(z\) 深度排序。 注意，这些列表仅为激活单元维护，而激活单元的数量总是恰好为 \(n + 1\)，因为 \(L\) 穿过所有 \(n\) 条线。 显然，这些列表提供了足够的信息来确定 \(\mathcal{A}\) 的每个单元的最前方多边形(foremost polygon)。 我不会详细说明当 \(L\) 扫描过顶点时算法的具体操作，只是提及算法的一个特征。当一个顶点被扫描时，旧单元"消亡(die)"，新单元变为激活状态， 它们所包含得多边形列表几乎相同。这种"连贯性(coherence)"可以被用来收集跨越扫描线的顶点的信息，从而将每个单元的更新成本保持在常数时间内。 于是就得到了一个最坏情况下为 \(O(n^2)\) 的消除隐藏面算法。

但是在实践中发现，这并不是最好的算法，因为它总是需要 \(\Omega(n^2)\) 的时间和空间，而大多数现实场景的复杂度要小得多。 由于在高质量图形中 \(n\) 大到 \(10^6\) 并不罕见，所以尽可能避免平方级时间复杂度非常重要。 对输出场景复杂度敏感的算法output-size sensitive，是当前研究比较多的课题(Dorward 1994)。

6.7.3. 外观图 (Aspect Graphs)

20世纪70年代末，计算机视觉领域的研究人员引入了"外观图(aspect graph)"的概念来辅助图像识别(Koenderink & van Doorn 1976, 1979)。 其思想是把所有可能得"特征视图(characteristic views)"dou存储下来，与实际看到的内容进行比较。对于多面体物体，特征视图由组合等价性(combinatorial equivalence)决定。 如果两个相机采集的图像具有相同的组合结构，即由多面体可见面在视平面上的投影所产生的平面图相同，那么两个相机看到的是多面体的相同外观(aspect)。 视觉空间划分(visual space partition, VSP)是将物体外部的所有空间划分为若干个外观恒定(constant aspect)的连通区域或单元。 外观图是VSP的对偶图(对偶图的含义见1.2.3节和4.4节)， 每个区域对应一个节点，共享同一面的区域之间用一条边连接。

排列为理解凸多面体的 VSP，以及因此产生的外观图，提供了一个清晰的框架。对于多胞体 \(P\)，VSP 正是由包含 \(P\) 各面(face)的平面(planes)所形成的排列(Plantinga & Dyer 1990)。 例如，考虑一个将空间划分为二十六个无界区域的立方体，如图 6.15 所示。其中包括六个矩形柱体，对应六个立方体面； 八个卦限，每个顶点关联一个；以及十二个"楔(wedge)"，每条边关联一个。考虑从点 \(p\) 观察立方体的视图，该点从一个单元 \(A\) 出发， 穿过排列的一个面 \(f\)，到达相邻的单元 \(B\)，如图所示。假设从单元 \(A\) 可以看到立方体的面 \(F\)，排列面 \(f\) 位于 \(F\) 所在的平面内。 那么当 \(p\) 位于 \(f\) 上时，它侧视 \(F\)(edge-on)。当 \(p\) 进入单元 \(B\) 时，\(F\) 将不再可见。因此，\(f\) 确实代表了外观的一个转换。

由定理 6.4.1 可以直接推出，具有 \(n\) 个顶点的凸多胞形的 VSP 大小为 \(O(n^3)\)， 并且可以在 \(O(n^3)\) 时间内构建。遍历 VSP 的即可获得外观图。

外观图也可以通过一般的非凸多面体定义，其组合复杂度在透视投影下会飙升至 \(\Theta(n^9)\)‼️ 参见 Gigus, Canny & Seidel(1991)。

6.7.4. 最小多胞体投影(Smallest Polytope Shadow)

考虑这样一个问题，给定的多胞体 \(P\)，在来自无穷远处的光源下，寻找一个正交投影，使其到平面上的面积最小。最早 McKenna & Seidel (1985) 和 McKenna (1989) 在研究这个问题， 他们给出了一种基于排列的解法。我将简要概述他们对排列的应用，而不详细解释他们的完整解法。

其主要内涵与外观图的基础相同。当观察点(viewpoint)穿过包含 \(P\) 的一个面的平面时，投影的组合结构会发生变化。该问题与 VSP 构造不同之处在于，观察点/光源位于无穷远处， 因此投影是正交投影而不是透视投影。从无穷远处的观察点来看，\(P\) 实际上缩小为一个点，所有的面所在的平面都包含该点。这给我们提供了以下方法。

设 \(\pi_f\) 是平行于 \(P\) 的面 \(f\) 且经过原点的平面。令 \(\mathcal{A}\) 是由 \(P\) 的所有面 \(f\) 对应的 \(\pi_f\) 形成的平面排列。 \(\mathcal{A}\) 将空间分割成以原点为顶点的无界锥体。任何表示光线方向的向量 \(u\) 都落在某个锥体内。该锥体决定了从无穷远处沿方向 \(u\) 观察的组合等价类， 因此也决定了在垂直于 \(u\) 的平面上的投影的组合结构。见图 6.16。

虽然对于同一锥体内的任何方向向量，投影的组合结构是恒定的，但投影的面积在整个锥体内并不是恒定的。McKenna 和 Seidel 证明最小面积是在 \(\mathcal{A}\) 的某条边上实现的， 即沿着由两个面所在平面的交线所确定的方向。

虽然 \(\mathcal{A}\) 是一个平面排列，根据定理 6.4.1其大小为 \(O(n^3)\)。 但由于所有平面都包含原点，所以它是高度退化的。事实上，它的大小只有 \(O(n^2)\)，正如下面的论证所示。

用平行于 \(xy\) 平面的平面 \(\pi\)，比如 \(\pi: z=1\) 与 \(\mathcal{A}\) 求交。\(\mathcal{A} \cap \pi = \mathcal{A}'\) 本身就是一个直线排列。 任何方向向量 \(u\) 都映射到 \(\pi\) 上的一个点，该点是 \(\pi\) 与包含 \(u\) 的直线的交点。 因此，所有无穷远处的视点(viewpoints)与二维排列 \(\mathcal{A}'\) 中的点一一对应，其复杂度为 \(O(n^2)\)。 最后，实现最小面积的视点对应于 \(\mathcal{A}'\) 的一个顶点，这一命题在 McKenna & Seidel(1985) 中得到了证明。

现在我们有了一个在 \(O(n^2)\) 时间内构建 \(\mathcal{A}'\) 的算法。我们无需构建 \(\mathcal{A}\)。对于 \(O(n^2)\) 中的每个顶点， 计算在垂直于由该顶点确定的方向的平面上的投影面积。返回最小的面积。

剩下的就是计算 \(\mathcal{A}'\) 的每个顶点产生的投影面积，这部分我将不作解释。有一种巧妙的方法可以避免在每个顶点重复计算面积，这样就可以在常数时间内处理每个顶点， 进而使总时间复杂度达到 \(O(n^2)\)(练习 6.7.5[1])。

6.7.5. 练习

1. 面积计算 Area calculation。
   1. 设 \(N\) 是一个面积法向量(area normal)，即垂直于面 \(F\) 的向量，其长度等于 \(F\) 的面积。 设 \(u\) 为观察方向。证明 \(F\) 投影到垂直于 \(u\) 的平面上的投影面积是 \(N \cdot u\)。
   2. 设 \(N_i\) 是面 \(F_i\) 的面积法向量。证明所有 \(F_i\) 的投影面积是 \((\sum N_i) \cdot u\)
   3. 利用 (b) 说明如何根据 \(A'\) 的每个顶点确定的方向来计算多胞体影子的面积。
2. 最大面积影子 Maximum area shadow。求单位立方体的最大面积影子，该影子是投影到垂直于光线的平面上的。

6.7.6. 切割火腿三明治 (Ham-Sandwich Cuts)

现在我们来探讨利用排列来寻找分离点集(separated sets of points)的火腿三明治割的美妙方法。点集的平分线(bisector)是一条直线，其两侧点的数量都不超过总数的一半。 为简单起见，我们只关注处于一般位置(任意三点不共线)的点。此外，我们将假设两侧点集各自包含奇数个点。因此，一个集合的平分线会经过(至少)一个点(练习 6.7.7[1] 要求去掉这一限制)。

首先考虑包含 \(n\) 个点的单个集合 \(A\) 的平分线。在上述假设下，该集合不会只有垂直平分线，因此我们可以安全地忽略它们。 根据6.5 节讨论的映射 \(\mathbb{D}\) 对 \(A\) 的点进行对偶化， 生成一个由 \(n\) 条直线组成的排列 \(\mathcal{A}\)。现在我们论证 \(A\) 的所有平分线精确地对偶于 \(\mathcal{A}\) 的中位层(median level) \(M_{\mathcal{A}}\)。 中位层是 \(\mathcal{A}\) 的边(及其连接顶点)的集合，这些边上的点在垂直方向上严格上方恰好有 \((n-1)/2\) 条直线(下方也有相同数量)。 根据引理 6.5.5，点 \(p \in M_{\mathcal{A}}\) 对偶于一条直线 \(\mathbb{D}(p)\)， 该直线下方的点数与 \(p\) 上方的直线数相同。根据中位层的定义，\(p\) 上方有 \((n-1)/2\) 条直线，所以 \(\mathbb{D}(p)\) 下方有 \(A\) 的 \((n-1)/2\) 个点，也就是说， \(\mathbb{D}(p)\) 平分 \(A\)。因此，\(\mathbb{D}(p)\) 是平分线当且仅当 \(p \in M_{\mathcal{A}}\)。

根据此引理，\(A\) 和 \(B\) 的火腿三明治割的直线，必然可对偶化为一个同时位于 \(M_{\mathcal{A}}\) 和 \(M_{\mathcal{B}}\) 上的点(其中 \(\mathcal{B}\) 是 \(B\) 的对偶排列)。 因此，所有的火腿三明治割都可以通过求这两个集合的中位层的交点来找到。

这两个层可能会以复杂的方式相交，但如果这两个集合可以通过一条直线分离，就会更简单。设 \(A'\) 和 \(B'\) 是两个可由直线分离的集合。 那么通过适当的平移和旋转，它们可以转换为被 \(y\) 轴分离的集合 \(A\) 和 \(B\)，不妨设\(A\) 在右\(B\) 在左。参见图 6.17 示例。 现在对两者应用对偶映射 \(\mathbb{D}\)。如图 6.18 所示，排列 \(A\) 中的直线都具有正斜率，而如图 6.19 所示，\(B\) 中的直线都具有负斜率。

因为 \(M_A\) 由正斜率的直线的子线段组成，所以它是严格单调递增的。同样，\(M_B\) 是严格单调递减的。两者在图 6.18 和 6.19 中均以阴影画出。 因此它们相交于一点，所以火腿三明治割是唯一的。图 6.20 显示它们相交于 \((-\frac{1}{6}, 2\frac{1}{3})\)，实际上直线 \(y = 2(-\frac{1}{6})x - \frac{7}{3}\) 就是图 6.17 中所示的那两个点集的火腿三明治割。

事实证明，可以在不完整构建排列的情况下，找到这个交点，对于包含 \(n\) 和 \(m\) 个点的集合，仅需 \(O(n + m)\) 的时间！ 该算法相当复杂，我不在此详述(Edelsbrunner 1987，pp. 336–45)。此外，对于未分离的点集，也能达到相同的线性时间复杂度(Lo, Matoušek & Steiger 1994)。 这为 Atallah(1985) 率先研究的一个有趣的匹配问题提供了最优算法，我们将在接下来描述它。

红蓝匹配(Red-Blue Matching)

给定平面上的 \(n\) 个红点和 \(n\) 个蓝点，任务是用不相交的线段将它们配对成红蓝点对。这些点可能是计算机视觉系统中平移物体的特征，该物体在连续的("红"和"蓝")帧之间发生了平移。 匹配之后就可以恢复这种平移。这是所有匹配线段不仅不相交，而且互为平移这一问题的特例。其他应用则没有这种长度限制。

一般的红蓝匹配问题可以通过一种分治的算法来解决，这种算法在每层都使用火腿三明治割。考虑图 6.21(a) 中 \(n=6\) 个红点和 6 个蓝点的集合。 首先，使用火腿三明治割将集合分成两组，每组包含三个红点和三个蓝点(图 (b) 中的割线 1)。然后，将这些集合中的每一个再分割，使得一个红点和一个蓝点在一侧， 而另一个红点和蓝点在割线(标记为 2 的割线)上。请注意，由于每种颜色的总数是奇数(在此例中为三个)，所以这些割线必须穿过点才能实现二等分，否则我们会剩下不平衡的数量。 最后，再次分离剩余的每对两点集合(虚线割线)。如图 6.21(b) 所示，现在用不相交的线段匹配这些点就是小菜一碟了。 最后的割线直接给出了它们分离出的匹配点对，有些匹配位于割线内部。需要澄清的是，此过程产生的匹配线段不会相交(练习 6.7.7[4])。

该算法的时间复杂度为 \(O(n \log n)\)，在 \(O(\log n)\) 层中的每一层寻找割线需要线性工作量。这可以通过归约到排序问题来证明是最优的。详情请参阅 Lo et al.(1994)。

更高维度 (Higher Dimensions)

最后我们需要提到，火腿三明治定理可以推广到更高维度:

6.7.7. 练习

1. [easy] 偶数个点 Even number of points。利用平分线(bisector)的定义，论证当 \(A\) 或 \(B\) 拥有偶数个点时，这些情况可以简化为拥有奇数个点的情况。
2. 中位层的大小 Size of median level。令 \(A\) 为如下点集，从原点画三条射线，彼此间隔 \(2\pi/3 = 120^\circ\)。 在每条射线上等间距地放置 \(n/3\) 个点。计算由 \(A\) 中点的对偶(duals)所形成的排列的中位层(median level)中的边数。
3. [Programming] 二分程序 Bisection program。编写一个程序，在给定的平面点集中找到一条平分线。除了点互不相同这一条件外，不对点做任何其他假设。
4. 红蓝匹配 Red-blue matching。证明由火腿三明治分治算法产生的匹配线段是互不相交的。