7.11 平面点定位
(Planar Point Location)

7.11.1. 应用 (Appllications)

在平面的某个细分区域定位一个点，是几何搜索中最基本的问题之一，这被称为平面点定位(Planar Point Location)问题。我们已经遇见过类似的搜索需求了，比如，构建梯形图(2.4.1 节)、在维诺图中搜索最近点(5.5.1 节)、搜索 k 阶维诺图中的 k 个最近邻(6.6 节)。

平面点定位的另一个常见应用是确定一个查询点是否位于给定的多面体内部。尽管我们已经在 7.5 节中提到了一种解决点在多面体中问题的方法，但该方法是一次性(single-shot)的，对于固定的多面体且需要重复查询不同点的情况效率不高。这个问题与平面点定位之间的联系可以通过 7.3.1 节中使用的三维到二维投影来理解。假设给定的多面体 \(P\) 位于 \(xy\) 平面上，令 \(P^+\) 为 \(P\) 中外法线具有非负向上分量的面集合，这些面的外法线 \(z\) 分量 \(\ge 0\)。这些面是从 \(z = +\infty\) 可见的面。令 \(P^-\) 为所有其他面的集合，它们的法线指向下方。将 \(P^-\) 投影到 \(z = 0\) 平面上，并将 \(P^+\) 投影到 \(z = h\) 平面上，其中 \(h\) 是 \(P\) 的高度。如此，在这两个平面上产生了两个细分区域，分别记为 \(S^+\) 和 \(S^-\)。现在，给定任何查询点 \(q\)，将其向上、向下投影，并在两个细分区域中定位它。假设它投影到 \(S^+\) 的面 \(f^+\) 上，这就选出了一个如图 7.31 所示的垂直棱柱(prism)。这就很容易判断 \(q\) 在这个棱柱中，是位于 \(f\) 的上方还是下方。如果它在 \(f\) 上方，则 \(q \notin P\)。如果在下方，则在下面那个的细分区域上重复该过程。当且仅当点位于由 \(S^+\) 中的搜索得到的 \(P\) 的面下方，并且位于由 \(S^-\) 中的搜索得到的 \(P\) 的面上方时，才有 \(q \in P\)。

7.11.2. 独立集算法(Independent Set Algorithm)

读者可能已经意识到，7.10 节中介绍的 Kirkpatrick 搜索结构为平面点定位问题提供了一个解决方案。事实上，这正是他最初的动机(Kirkpatrick 1983)。唯一的复杂之处在于，一般的平面细分可能包含一般的多边形面，这些面需要通过多边形三角分割算法进行三角化。在这一步之后，我们就可以像处理多面体层次结构那样继续进行，区别在于删除顶点产生的每个孔洞都需要通过多边形三角分割算法重新进行三角化。与多面体情况一样，对每个孔洞重新三角化只需要常数时间，因为这些孔洞最多只有八个顶点。

定理 7.11.1. \(n\) 个顶点的多边形平面细分可以在 \(O(n)\) 的时间和空间内进行预处理，从而可以在 \(O(\log n)\) 时间内完成平面点的定位。

7.11.3. 单调细分 (Monotone Subdivisions)

尽管 Kirkpatrick 的搜索结构在某种意义上解决了平面点定位问题，但它既不是第一个达到这些边界的算法，也不是最新的。Dobkin & Lipton(1976) 早期提出的一种算法使用了二次空间，非常简单，并且实现了更好的查询常数。查询可以通过 \(2 \log n\) 次比较来完成。Lipton & Tarjan(1980) 是第一个实现了 \(O(n)\) 的预处理和 \(O(\log n)\) 查询时间的算法，但他们的算法过于复杂，不切实际。Kirkpatrick 的算法优雅且非常适合多面体，但其较高的查询常数使其在一般的平面细分搜索中不具备吸引力。

一种常用的平面点定位方法依赖于单调细分。如果一个细分的每个面都是单调的(例如相对于水平方向)，则该细分就是单调的。如果一个面与每条垂直线的交集是一个连通集，即，一个点或一条线段，见 2.1 节，那么这个面就是单调的。许多常见的细分都是单调的，三角分割、诸如维诺图或 \(k\)阶维诺图的任何凸分割、以及直线排列。那些非单调的细分可以被进一步划分，以产生单调细分。例如，通过对每个面进行三角分割。这些细分的实用性已被 Lee & Preparata(1977) 所认识，并在此后得到了深入的研究。

我们现在粗略的概述单调细分搜索背后的一些主要思想。将单调细分中的"分隔线(separator)"定义为细分中边的连通集合，这些边与每条垂直线恰好相交一次。这些是垂直方向上的单调链，它们将细分分成上下两部分。

核心思想是找到一组分离链，将细分划分成水平条带(horizontal strips)。然后进行双重二分搜索，在这些条带上进行垂直搜索，将查询定定位在两个分隔线之间，以及进行水平搜索将其定位在一个条带内。

如图 7.32 所示。该细分是一个维诺图，它一定是单调的。图中显示了四个分隔线。\(S_1\) 是最低的，其下方只有点 1 的维诺单元\(C_1\)。\(S_2\) 是次高的，其下方有 \(C_2\) 和 \(C_1\)。请注意，\(S_2\) 在其整个长度上都位于 \(S_1\) 的上方。类似地，\(S_3\) 位于 \(C_3\) 上方，\(S_4\) 位于 \(C_4\) 上方。这个过程可以继续下去，找到一组分隔线 \(S_1, S_2, \dots, S_m\)，可以认为它们在垂直方向上是排序的，每对相邻的分隔线之间都夹着细分的一个单元。

考虑判定一个查询点 \(q\) 是在某个特定分隔线 \(S_i\) 的上方还是下方的问题。这可以通过对 \(S_i\) 顶点的 \(x\) 坐标和 \(q\) 的 \(x\) 坐标进行水平二分搜索来完成，因为 \(S_i\) 关于 \(x\) 轴是单调的。一旦 \(q\) 在 \(x\) 轴上的投影定位在 \(S_i\) 的某条边 \(e\) 的两个端点之间，就可以测试它是在 \(e\) 的上方还是下方。由于任何 \(S_i\) 都有 \(O(n)\) 条边，因此查询 \(q\) 在 \(S_i\) 的上方还是下方，可以在 \(O(\log n)\) 时间内得到回答。

现在，这个查询可以重复使用，来对分隔线集合进行二分搜索。首先查询 \(q\) 是在 \(S_{m/2}\) 的上方还是下方。如果在下方，则查询它与 \(S_{m/4}\) 的关系。如果在上方，则查询 \(S_{3m/4}\)，依此类推。这种二分搜索将需要 \(O(\log m)\) 步，每步的成本为 \(O(\log n)\)。由于 \(m = O(n)\)，总查询时间为 \(O(\log^2 n)\)。

当然，这在渐近意义上比定理 7.11.1 的结果要差。此外，由于共享边的程度很高，如图 7.32 所示，存储分隔符可能需要二次的空间。然而，该算法简洁明了，可以通过改进查询时间和空间需求，来达到与定理 7.11.1 所声称的相同的渐近复杂度。这些改进绝非易事，需要拓扑排序和分数级联(Fractional Cascading)技术(Chazelle & Guibas 1986a; Chazelle & Guibas 1986b)等思想的出现。详见 Edelsbrunner(1987, Chapter 11.)。

7.11.4. 随机梯形分解(Randomized Trapezoidal Decomposition)

随机算法为点定位问题提供了一种相对较新且极具吸引力的替代方案。这里我们介绍 Seidel(1991) 提出的此类算法，该算法在第 2 章中已有所提及。在2.4.1 节中，我们使用梯形分解来对多边形进行三角分割。同样的通用技术也适用于比多边形更一般的对象。特别是，它适用于不相交noncrossing线段集合，任意两条线段之间均无交点，但它们可以共享端点。注意，多边形的边满足这一定义。设 \(S = \{s_1, \dots, s_n\}\) 是一个不相交线段的集合。目标是从每个线段端点向左右两侧延伸水平弦(chord)，将平面划分为梯形。这些梯形由两条水平边组成，其中一条边可能是退化的，即长度为零。面可能无界，但是有时为了方便，用一个大的轴对齐矩形包围 \(S\) 以确保所有梯形都是有界的。见图 7.33。梯形数量为 \(O(n)\)。练习 7.11.5[1] 要求证明 \(3n + 1\) 是一个紧上界。

为了简化细节，我们假设任意两个端点都不在同一条水平线上，见2.2 节。这限制了邻接关系：

引理 7.11.2. 每个梯形至多有两个上方相邻的梯形和两个下方相邻的梯形，且邻接梯形共享一段长度非零的水平弦。

证明: 假设一个梯形有三个上方相邻的梯形。构成其上侧的三段水平弦不可能源自同一个端点，因为每个端点至多产生两条弦。一条向左，一条向右。因此，这个上侧必须包含至少两个顶点，这违反了任何两个端点不在同一水平线上的假设。□

该引理允许我们用二叉搜索树来表示梯形位置，之所以是二叉的，是因为每个梯形最多只有两个邻居。这种巧妙的搜索结构开发于20世纪70年代末，并由 Preparata(1981)明确使用。本文根据Seidel(1991)详细介绍该算法，其中梯形分解算法源于 Mulmuley(1990)的工作。

搜索树有三种类型的节点:

内部 \(X\) 节点，在线段 \(s_i\) 的左侧或右侧
内部 \(Y\) 节点，在线段端点的上方或下方分支
叶梯形节点

搜索树是增量构建的。设 \(s = ab\) 是要添加到现有结构中的新线段。结构的更新可以分为几个步骤:

添加端点 \(a\) 和 \(b\)。对于每个端点，通过在树中搜索找到包含它的梯形。用一个 \(Y\) 节点分割这个梯形。
添加线段 \(s\)。
1. 让 \(s\) 穿过分割区域，识别出每个被 \(s\) 切割的梯形。
2. 在 \(s\) 的每一侧，合并左右边界线段相同的梯形。
3. 为所有被 \(s\) 分隔的梯形创建 \(X\) 节点。

现在，我们来构建三个特定线段 \(\{s_1, s_2, s_3\}\) 的搜索树。虽然细节有些繁琐，但耐心终将会有回报，你会更加欣赏最终数据结构的优美之处。在图 7.34 到图 7.39 中，下方的边画在上方边的左侧，左边画在右边的左侧。

添加 \(a_1\)。将原始区域，或者说是整个平面，分割为上方区域 \(A\) 和下方区域 \(B\)。创建节点 \(Y(a_1)\) 作为它们的父节点。
添加 \(b_1\)。定位 \(b_1 \in B\)。将 \(B\) 划分为 \(C\) 和 \(D\)，并创建节点 \(Y(b_1)\) 作为它们的父节点。
线段 \(s_1\)，将 \(C\) 划分为 \(E\) 和 \(F\)，分别位于 \(s_1\) 的左侧和右侧，并创建节点 \(X(s_1)\) 作为它们的父节点。此时的搜索树如图 7.34 所示。
添加 \(a_2 = a_1\)。结构不发生变化。
添加 \(b_2\)。定位 \(b_2 \in D\)。将 \(D\) 划分为 \(G\) 和 \(H\)，并创建节点 \(Y(b_2)\) 作为它们的父节点。见图 7.35。
线段 \(s_2\)，将 \(F\) 划分为 \(I\) 和 \(J\)，并将 \(G\) 划分为 \(K\) 和 \(L\)，两者均有各自的 \(X(s_2)\) 父节点。见图 7.36。
沿 \(s_2\) 合并。将 \(J\) 和 \(L\) 合并为一个区域 \(M\)，因为它们共享相同的左右边界线段 \(s_2\) 和 \(+\infty\)。相应地重新连接。见图 7.37。
添加 \(a_3\)。定位 \(a_3 \in I\)，并使用节点 \(Y(a_3)\) 将其划分为 \(N\) 和 \(O\)。
添加 \(b_3\)。定位 \(b_3 \in K\)，并通过节点 \(Y(b_3)\) 将其划分为 \(P\) 和 \(Q\)。见图 7.38。
线段 \(s_3\)，将 \(O\) 划分为 \(R\) 和 \(S\)，并将 \(P\) 划分为 \(T\) 和 \(U\)，两者均具有各自的父节点 \(X(s_3)\)。
沿 \(s_3\) 合并。将 \(S\) 和 \(U\) 合并为一个梯形 \(V\)。见图 7.39。

我们用图 7.39 中的最终搜索树，在梯形 \(V\) 中定位点 \(q\)。点 \(q\) 位于 \(a_1\) 和 \(b_1\) 之下，但在 \(b_2\) 之上，因此从根节点出发，路径会依次向左、向左、向右弯曲。 \(q\) 位于 \(s_2\) 的左侧，因此在 \(X(s_2)\) 节点处选择左分支。\(q\) 位于 \(b_3\) 之上，最终定位于 \(s_3\) 的右侧。图中高亮显示了通往 \(V\) 的搜索路径。请注意，并非所有梯形都有从根节点出发的唯一路径。如果 \(q\) 在 \(V\) 中但位于 \(b_1\) 之上，那么可以通过另一条路径到达 \(V\)。

从我们的描述中可以明显看出，所获得的搜索结构取决于插入线段的顺序。"坏"的顺序可能会导致高度为 \(\Omega(n)\) 的瘦高树。"好"的顺序将产生高度为 \(O(\log n)\) 的矮胖树。查询时间与这个高度成正比。正如 2.4.1 节中提到的，如果线段是按随机顺序添加的，即 \(n!\) 种顺序中的每一种出现的概率均等，那么可以证明其期望高度为 \(O(\log n)\)。此外，构建整个结构的期望时间为 \(O(n \log n)\)。虽然这些期望值可能较弱，因为他们是掩盖性能不佳的宽泛平均值，但实际上可以进一步证明，树高显著超过 \(O(\log n)\) 的概率很小。因此，这种简洁且实用的算法在期望 \(O(n \log n)\) 的预处理时间下，实现了期望 \(O(\log n)\) 的查询时间。

平面点定位仍然是一个活跃的研究领域。不仅这里讨论的基本问题仍有改进的空间，而且在撰写本文时，两个重要的相关问题也处于不断变化的状态， "动态"平面点定位，其细分会变化，例如，通过插入或删除维诺站点来改变细分；以及三维及更高维空间细分中的点定位。

7.11.5. 练习