7.10 多面体极值点查询
(Extremal Polytope Queries)

寻找多面体的极值点比上一节讨论的二维情况要困难得多。这并没有直接对应于我们在凸多边形边界链上所使用的一维搜索的方法。多面体的二维表面在搜索方向上提供了过大的自由度。尽管如此， Kirkpatrick(1983) 发明了一种极其精妙的搜索结构，使得该问题能够在 $O(\log n)$ 的查询时间内解决，渐进时间复杂度与二维情况相同，尽管我们将看到其比例常数更大。

7.10.1. 思路概要 (Sketch of Idea)

该算法的核心思想是，在给定的多面体 $P$ 中嵌套一系列越来越简单的多面体。最内层的多面体是一个四面体或三角形，总共有 $O(\log n)$ 个多面体。构建这个多面体层级结构的时间复杂度为 $O(n)$，并且存储它们也需要 $O(n)$ 空间。一旦构建完成，极值查询就可以在 $O(\log n)$ 的时间内得到答案。值得注意的是，尽管这与寻找凸多边形的极值点的时间复杂度相当，但那些多边形并不需要预处理。当然将一个多边形读入内存也需要 $O(n)$ 时间，这可以被视为一种粗略的预处理。

查找多面体极值点的过程如下。首先找到最内层多面体的极值点，然后以此为起点，沿着层级结构向外推，直至 $P$。假设嵌套多面体的序列为 $P = P_0, P_1, P_2, \dots, P_k$，其中 $P_k$ 在最内层。我们用 $a_i$ 标记多面体 $P_i$ 的极值点。先比较 $P_k$ 的三或四个顶点来找到其极值点 $a_k$。$a_k$ 及其他一些信息将为我们提供 $P_{k-1}$ 中一小部分候选顶点。检查它们的极值性，将得出 $a_{k-1}$。由此我们找到 $a_{k-2}$，依此类推。结果表明，在从一个多面体移动到下一个多面体所需的工作量是常数级的。因为 $k = O(\log n)$，所以找到 $a_0$ 的总时间也是 $O(\log n)$。下面我们继续详细介绍搜索结构和算法。

7.10.2. 独立集合 (Independent Sets)

回想一下4.1.4节，多面体的边和顶点构成一个平面图。图7.21(a)显示了二十面体(icosahedron)的图，图7.22 是我们将在本节中用来阐释相关概念的例子。Kirkpatrick 的核心思想依赖于图论中"独立集合 independent set"的概念。如果图 $G$ 中的一组节点 $I$ 中任意两个节点都不相邻，那么我们就称集合 $I$ 为独立集合。因此，它们在某种意义上是分散的。图7.21(a)中标出了这样一个独立集。这三个节点的集合实际上是这个图的一个最大独立集，因为不存在四个节点构成独立集合的情况。对于 Kirkpatrick 的方案来说，平面图具有完全由小度顶点(相邻节点数量少)构成的大独立集和至关重要。稍后我们会精确定义这些模糊的限定词。

嵌套在 $P = P_0$ 内部的第一个多面体 $P_1$ 的构造过程如下。如图 7.21(a) 所示，首先找到 $P_0$ 的一个独立顶点集，然后从图中将这些顶点及其所有关联边都删除，结果如图7.21(b)所示。因为这些顶点是独立的，每次删除都会在图中产生一个新的面。在图7.21(b)中，删除操作产生一个五边形，由于图中有两条边共线，所以看起来像是四边形。接下来，对这些面进行三角分割，参见图7.21(c)。在我们的例子中，可以任意地对它们进行三角分割，7.10.4节将对此进行更详细的讨论。在多面体上，与此操作对应的几何操作是，删除独立集合中的顶点并取剩余顶点的凸包。这将生成多面体 $P_1$，显然它嵌套在 $P_0$ 内部，因为它是 $P_0$ 顶点子集的凸包。图 7.23 显示了与图 7.21(c) 中的图相对应的 $P_1$。请注意，五边形(图中有两个可见)由三个共面三角形组成。通常，与被删除的独立顶点相邻的顶点不会共面。在本例中，它们共面是因为二十面体的对称性。正是共面性和凸性，允许我们任意地对其进行三角分割。通常，我们需要取新面边界周围顶点的凸包来进行三角分割。

现在重复该过程以构造 $P_2$。识别出 $P_1$ 的一组独立顶点，如图 7.21(c) 所示。删除这些顶点，产生图 7.21(d) 所示的图。恰好，这次删除只产生了三角形面，因此不需要进一步的三角分割。读者可能会认出图7.21(d)是八面体的 Schlegel 图，相应的多面体 $P_2$ 是一个(nonregular)八面体，如图 7.24 所示。再重复此过程一次。图 7.21(e) 中识别出了一个大小为 2 的独立集。删除操作产生了图 7.21(f) 所示的图。对两个四边形面(其中一个是外部面)进行三角分割，得到图 7.21(g)，这是一个四面体的图像。图 7.25 展示了这个四面体，同样由于二十面体的对称性，它由四个共面点组成。

7.10.3. 独立集合: 性质和算法 (Independent Sets: Properties and Algorithm)

为了获得具有合适性质的嵌套多面体的层次结构，独立集不能随意选择。幸运的是，正如 Kirkpatrick(1983) 针对任意平面图所展示的那样，获得合适的性质是很容易的。对于多面体的图，论证稍微简单一些，这里我沿用 Edelsbrunner(1987) 的表述。

为了仅计算 $O(\log n)$ 个多面体，需要每一步都删除常数比例的顶点。假设我们可以在任何具有 $n$ 个顶点的多面体上找到一个包含 $cn$ 个顶点的独立集，其中 $c < 1$。那么在每一步，我们将顶点数量减少 $(1-c)$ 倍，因此在 $k$ 步之后，我们将拥有 $n(1-c)^k$ 个顶点。当 $k$ 为特定值时，该数量达到 4:

$$ \begin{equation}\label{f7.10} \begin{aligned} n(1 - c)^k &= 4, \\ \log n + k \log(1 - c) &= 2, \\ k &= \frac{\log n}{-\log(1 - c)} - \frac{2}{-\log(1 - c)} \end{aligned} \end{equation}\tag{7.10} $$

由于 $(1-c) < 1$，则 $-\log(1-c) > 0$，且式 7.10 的右边是一个正的常数乘以 $\log n$减去另一个常数。因此它是 $O(\log n)$。例如，对于 $n = 2^{20} \approx 10^6$ 和 $c = 1/10，k = 118$。因此，我们的目标是证明每个多面体图都有一个大小为 $cn$ 的独立集，其中 $c < 1$。

以下贪心过程是寻找独立集合最自然的方法。选择一个度数最低且不与任何先前选择的顶点相邻的顶点。直观理解是，低度数顶点会尽可能少的淘汰其他候选顶点。虽然这种简单的算法不一定会找到最大独立集，但它足以满足我们的需求。我们甚至可以稍微放宽一些条件，选择任何度数不太高的顶点。这避免了搜索度数最低的顶点。具体来说，我们使用算法 7.4。显然，该算法可以产生一个独立集，并且在具有 $n$ 个节点的平面图上以 $O(n)$ 的时间复杂度运行。但不太清除的是，它生成的独立集是否够大。这是由 Edelsbrunner(1987, Theorem 9.8) 提出的以下定理所确定的。该定理生成算法 7.4 能达到常数 $c = 1/18$。

定理 7.10.1. 由算法 7.4 生成的具有 $n$ 个顶点的多面体图 $G$ 的独立集 $I$ 的大小至少为 $n/18$。

证明: 证明的关键在于欧拉公式 $V - E + F = 2$。我们在 4.1.5 节中用公式 (4.4) 确定了，多面体图的边数有上界 $3V - 6: E \le 3n - 6$。现在我们利用这个结论得到 $G$ 所有节点度数之和 $\Sigma$ 的上界。因为每条边有两个端点，所以它将 $G$ 的每条边计算了两次。因此 $\Sigma \le 6n - 12$。

这个度数之和的上界直接直接表明，必然存在许多度数较小的节点。因为如果所有节点度数都很高，它们的度数之和将超过这个界限。从数量上看，至少有 $n/2$ 个顶点的度数 $\le 8$。否则假设，有超过 $n/2$ 个节点的度数 $\ge 9$。仅这些节点的度数之和就 $\ge 9n/2$。其他每个节点的度数必须 $\ge 3$。为了简化计算，让我们假设 $n$ 是偶数。$\Sigma$ 的最小值将出现在只有一半节点具有高度数，而另一半度数尽可能低的时候。因此

$$ \begin{equation}\label{f7.11} \Sigma \ge 9n/2 + 3n/2 = 6n \tag{7.11} \end{equation} $$

这与我们上面建立的上界 $6n - 12$ 矛盾。对于 $n$ 为奇数的情况，也可以得出类似的矛盾(练习 7.10.6[2])。因此我们已经证明，$G$ 中至少有一半的节点度数 $\le 8$，因此它们是算法 7.4 构建的独立集的候选顶点。剩下的任务是证明该算法选择了"大量"的这些候选顶点。

每当算法选择一个节点 $v$ 时，它会标记 $v$ 及其所有邻居。最坏的情况是 (a) 所有被标记的节点之前都没有被标记；并且 (b) $v$ 的度为最大可能值 8。设 $m$ 为 $G$ 中度数 $\le 8$ 的未标记节点数量。一个例子或许能更清楚地说明这些关系。假设 $m = 90$。选择一个节点 $v$，在最坏的情况下，需要标记 8 个未标记的节点。这将使 $m$ 减少了 9，变为 81。再次在这 81 个节点中选择一个，最坏情况下，$m$ 减少了 9。显然，至少会有 $1/9$ 的 $m$ 个节点被添加到独立集 $I$ 中。因此，当 $m = 90$，$|I| \ge 10$。

由于我们之前已经证明 $m \ge n/2$，由此 $|I| \ge n/18$。由此，我们确立了算法 7.4 总是能产生一个大小至少为原图 $1/18$ 的独立集。□

当 $c = 1/18$ 时，嵌套多面体的数量(根据公式 7.10)小于 $12.13 \log n$。这个比例常数并不理想，但总是选择度数最小的未标记节点可以将 $c$ 改进为 $1/7$(Edelsbrunner 1987，Problem9.9(d))，并将对数常数改进为 4.50。

7.10.4 构造嵌套多面体层级结构 (Construction of Nested Polytope Hierarchy)

现在我们详细说明如何构造该层次结构。在算法 7.5 所示的伪代码中，$N(v)$ 表示 $v$ 的邻居集合，即所有与 $v$ 相邻的顶点。

空间需求 (Space Requirements)

我们已经确定多面体层次结构的高度为 $O(\log n)$。咋一看，构建该层次结构所需的时间和空间似乎是 $O(n \log n)$，即每层是线性的，但实际上，由于层次结构各层之间按比例缩减，所以总量上是线性的。特别是，当 $c = 1/18$，每个多面体的顶点数最多是其父级的 $17/18$。因此，总大小不超过 $$ n \left[ (17/18) + (17/18)^2 + (17/18)^3 + \dots \right] $$ 虽然 $(1 - c)$ 的幂次和只有 $k$ 项，但通过让其延伸至无穷大来获得一个上界更容易。这样它就是熟悉的几何级数，其和为: $$ \frac{1}{1 - (1 - c)} = \frac{1}{c} = 18 $$ 因此，所需的总存储空间最多为 $18n = O(n)$。同样，构造时间也是 $O(n)$，尽管这需要一些此处未提供的论证。

重新三角分割的孔洞 (Retriangulating Holes)

我们之前提到过，当从 $P_i$ 中删除一个顶点 $v$ 时，必须对由此产生的孔洞进行适当的三角分割，以生成 $P_{i+1}$。设 $N(v)$ 为 $v$ 的邻居。通常情况下，它们不会共面，因此任意三角分割是不够的。我们需要计算 $N(v)$ 的凸包，并使用该凸包的外表面来提供三角分割。在实践中，我们可能需要在每一步重新计算整个凸包，才能从 $P_i$ 构造出 $P_{i+1}$，但这会导致 $O(n \log n)$ 的时间复杂度。但请注意 $|N(v)| \le 8$，因为 $v$ 的度数 $\le 8$。这意味着每个孔洞都可以在常数时间内用三角形修补好。并且整个层次结构构造所需的孔洞修补总数不超过删除顶点数的常数倍，即 $O(n)$。

连接多面体 (Linking Polytopes)

为了辅助搜索，需要用链表将层次结构中相邻位置的多面体连接起来。因为在层次结构构造的每一步，删除的顶点，构成一个独立集，所以两个相邻多面体的顶点、边和面之间的关系是明确的。我们在此不做详细说明(参见 Edelsbrunner (1987, pp.199–200))，而是假设我们需要的任何合理链接都是可用的。

7.10.5 极值点算法 (Extreme Point Algorithm)

现在我们将利用该层次结构来解决极点查询问题。我们将以寻找多面体的最高点，即 $z$ 坐标最大的顶点，为例来解释该算法，该过程也同样适用于寻找任意方向 $u$ 上的极值点。该算法最初由 Edelsbrunner & Maurer(1985) 详细阐述，另见 Edelsbrunner(1987, Section 9.5.3)。

设 $a_i$ 为多面体 $P_i$ 的一个最高点。为简化表述，我们假设对于每个 $i$，$a_i$ 都是唯一的。该算法的核心在于通过暴力穷举出最内层多面体 $P_k$ 的最高点 $a_k$，然后利用 $a_k$ 辅助找到 $a_{k-1}$，再利用 $a_{k-1}$ 找到 $a_{k-2}$，依此类推，直到 $a_0$，即原始多面体 $P_0 = P$ 的最高点。这个过程可以看作是一个垂直于 $z$ 轴的平面 $\pi$ 从 $a_k$ 开始，经过 $a_{k-1}$，逐层提升，最终移动到 $a_0$ 的过程。由于多面体是嵌套的，这个平面只向上移动。如图 7.26 所示，其中最内层的多面体是一个三角形未画出。

该算法的关键在于 $a_{i+1}$ 与 $a_i$ 之间的关系。我们将这种关系概括为下面的引理 7.10.2 和 7.10.3。第一个引理或许最容易理解，我们可以想象 $\pi$ 从 $a_i$ 向下移动到 $a_{i+1}$。

引理 7.10.2. 设 $a_i$ 和 $a_{i+1}$ 分别是 $P_i$ 和 $P_{i+1}$ 中唯一最高顶点。那么，要么 $a_i = a_{i+1}$，要么 $a_{i+1}$ 是与 $a_i$ 相邻的顶点中最高的那一个。

证明: 我们分两种情况讨论。首先，假设 $a_i$ 既是 $P_i$ 的顶点也是 $P_{i+1}$ 的顶点。因为 $P_i \supset P_{i+1}$，所以 $P_{i+1}$ 的任何顶点都不可能高于 $P_i$ 的最高点，因此在这种情况下，$P_{i+1}$ 的最高顶点 $a_{i+1}$ 必定就是 $a_i$。

其次，假设 $a_i$ 是在构建 $P_{i+1}$ 过程中被删除的顶点之一。设 $P_{i+1}$ 中的 $b_{i+1}$ 是 $P_i$ 中与 $a_i$ 相邻的顶点里的最高点。该引理的断言，$b_{i+1}$ 即为 $P_{i+1}$ 的最高顶点。

考虑 $P_i$ 中与 $a_i$ 相邻的面所构成的锥体。见图 7.27。该锥体的无限延伸部分记为 $C$。根据 $P_i$ 的凸性，有 $C \supset P_i$。又根据嵌套关系，有 $C \supset P_i \supset P_{i+1}$。因此 $a_{i+1} \in C$。但 $P_{i+1}$ 的任何顶点都不可能位于 $a_i$ 下方的伞状区域 $U = C - P_{i+1}$ 内。所以 $a_{i+1}$ 必须位于 $C$ 的另一部分，即 $C - U$ 中，而这一部分必然低于 $b_{i+1}$ 的高度，如图 7.28 所示。因此 $b_{i+1} = a_{i+1}$。□

该引理的一个直接推论是，$a_i$ 要么与 $a_{i+1}$ 相同，要么与 $a_{i+1}$ 相邻。乍一看，这似乎给了我们从 $a_{i+1}$ 跃升到 $a_i$ 的"钩子 hook"。但实际上这还不够，因为我们无法确定与 $a_{i+1}$ 相邻的顶点数量。如果我们要遍历所有这些邻居来寻找 $a_i$，虽然算法能正确运行，但其时间复杂度将是 $O(n)$ 而不是我们期望的 $O(\log n)$。我们需要一个更直接的从 $a_{i+1}$ 跃升到 $a_i$ 的钩子。

极值边 (Extreme Edges)

如果将 $P_{i+1}$ 投影到与 $\pi$ 正交的平面上，比如 $xz$ 平面，那么 $\pi$ 变成一条直线，$P_{i+1}$ 变成一个凸多边形 $P'_{i+1}$，如图 7.29 所示。我们用一撇(prime)表示投影到 $xz$ 平面上的对象。定义 $L_{i+1}$ 和 $R_{i+1}$ 为 $P_{i+1}$ 的两条边，它们投影到与 $a'_{i+1}$ 相连的 $P'_{i+1}$ 的两条边上。

现在定义 $P_{i+1}$ 中边 $e$ 的"伞形父节点(umbrella parents)"(或简称父级) 为 $P_i$ 中衍生出该边的顶点。其具体含义为，如果 $e$ 是 $P_{i+1}$ 的边，但不是 $P_i$ 的边，那么它位于 $P_i$ 的某个顶点 $v$ 的下方，与该顶点关联的面形成一种伞形结构，我们将删除该结构以生成 $P_{i+1}$。这个 $v$ 就是 $e$ 的唯一父节点。这一点在图 7.23 中最为明显，其中上方五边形面的两条对角线位于一个度为 5 的顶点下方。如果 $e$ 既是 $P_{i+1}$ 的边也是 $P_i$ 的边，那么它的父节点是 $P_i$ 中与 $e$ 相邻的两个三角形面的顶点。这两个顶点可能是也可能不是 $P_{i+1}$ 的顶点。

关键的引理是:

引理 7.10.3. 设 $a_i$ 和 $a_{i+1}$ 分别是 $P_i$ 和 $P_{i+1}$ 的唯一最高顶点。那么要么 $a_i = a_{i+1}$，要么 $a_i$ 是极值边 $L_{i+1}$ 和 $R_{i+1}$ 的父节点中最高的那个。

在证明之前，我们先探讨一下它的推论。如果已知 $P_{i+1}$ 的极值顶点 $a_{i+1}$，以及极值边 $L_{i+1}$ 和 $R_{i+1}$，我们可以通过检查引理提供的最多五个候选点来找到 $P_i$ 的极值顶点 $a_i$。如果我们能在常数时间内找到 $P_i$ 的新极值边 $L_i$ 和 $R_i$，我们就能在常数时间内完成一个完整的层级跃升，其总体复杂度为 $O(\log n)$。

那么已知 $a_i$，如何计算极值边呢? 有两种情况需要考虑：

$a_i \ne a_{i+1}$。这种情况我们可以使用暴力搜索来寻找极值边。原因在于，这种搜索的时间复杂度取决于 $a_i$ 的度数。当我们首次在多面体层级结构中遇到它时，它是一个独立顶点，在层级结构的构造过程中将被选择删除，因此其度数 $\le 8$。
$a_i = a_{i+1}$。此时不适合使用暴力搜索，因为如果我们遍历层级结构的多个层级而极值顶点保持不变，它的度数会通过边的"累积(accretion)"而变得越来越大。我们只能保证首次遇到时，其度数 $\le 8$。这种累积在图 7.26 的层级结构中最内层的三个多面体中是显而易见的。幸运的是，新的极值边与旧的很接近，$L_i$ 要么是 $L_{i+1}$，要么与 $L_{i+1}$ 的一个父节点相邻，$R_i$ 同理。我不会证明这个命题(练习 7.10.6[3])。

因此，在这两种情况下，都可以在常数时间内找到新的极值边。现在我们来证明引理 7.10.3。

证明: 假设 $a_i \ne a_{i+1}$。那么 $a_i$ 在 $\pi$ 之上。显然，$P_i$ 在 $xz$ 平面上的投影是一个凸多边形 $P'_i$，它包含投影 $P'_{i+1}$。如果考虑 $a'_i$ 的可能位置，如图 7.30 所示，很明显 $a_i$ 必须位于极值边 $L_{i+1}$ 和 $R_{i+1}$ 中的一个或两个至上。这就是引理的内涵。

图中从 $a'_i$ 出发的虚线连接为什么是合理的呢? 首先，$P_i$ 中所有与 $a_i$ 相邻的顶点也是 $P_{i+1}$ 的顶点。因此，投影中的边从 $a'_i$ 发出并终止于 $\pi$ 下方的 $P'_{i+1}$ 中。其次，$P_i \supset \text{conv} \{a_i \cup P_{i+1}\}$，因此通过 $a'_i$ 支撑 $P'_{i+1}$ 的两条切线位于 $P'_i$ 中。第三，不可能从 $a'_i$ 出发并且位于这些切线之外的边，因为这样的边无法终止于 $P'_{i+1}$ 中。因此，$P'_i$ 的边界包含了 $a'_i$ 处的切线，图 7.30 准确地描绘了这一点。

显然，$a'_i$ 处的切线必须包含 $P'_{i+1}$ 的至少一条极值边，并且 $a_i$ 是这条边的父节点，我们便证明了该引理。□

我们可以用算法 7.6 中显示的伪代码来总结该算法。根据引理 7.10.2 和 7.10.3，以及练习 7.10.6[3]，该算法将正确运行。现在剩下的唯一问题是其时间复杂度。我们已经确保算法在每一层所做的工作量都是常数级的。这就确定了算法的查询时间，搜索层次结构的 $O(\log n)$ 层，且每一层的工作量是常数。忽略一些细节，我们确立了以下定理:

定理 7.10.4. 经过 $O(n)$ 复杂度的时间和空间预处理后，多面体极点查询可以在 $O(\log n)$ 的时间内完成。

该定理的一个重要应用是碰撞检测。检测两个分别具有 $n$ 和 $m$ 个顶点的凸多面体是否相交。将每个多面体表示为一个层次结构，并利用练习 7.10.6[8]，可以根据下一层多面体之间的间距，有效地计算层次结构中相同层级的多面体之间的间距。 it is possible to compute efficiently the separation between the polytopes at a common level of the hierarchy from the separation between the polytopes at the level below. 这导出了一种 $O(\log n \log m)$ 的相交检测算法 (Dobkin & Kirkpatrick 1983)。

7.10.6. 练习

[easy] 最内层多面体 Innermost polytope。为什么层次结构中的最内层多面体顶点数不能 $\ge 5$ ?
$n$ 为奇数 $n$ odd。在定理 7.10.1 的证明中，我们只涵盖了 $n$ 为偶数的情况。请仿照该论证过程讨论 $n$ 为奇数的情况，证明结论仍然成立。
$a_i = a_{i+1}$。论证如果在算法 7.6 中 $a_i = a_{i+1}$，则 $L_i$ 要么是 $L_{i+1}$，要么与 $L_{i+1}$ 的父节点相邻。说明它们如何保证以常数找到 $L_{i+1}$。
嵌套多边形层次结构 Nested Polygon Hierachy。开发一种方法，在一个给定的具有 $n$ 个顶点的凸多边形内部构建一个包含 $O(\log n)$ 个凸多边形的层次结构。利用此方法设计一个能在 $O(\log n)$ 时间内完成的极值点算法。
[easy] 常数 $c$ The constant c。计算图 7.26 中的平均常数 $c$，并利用此值根据公式 7.10 计算 $k$。
[Programming] 独立集算法的实现 Implementation of independent set algorithm。编写一个程序，使用算法 7.4 在给定图中查找一个独立集。
[Programming] 嵌套多面体的实现 Nested polytope implementation。使用第 4 章中的凸包算法和上一练习中的独立集算法，在 $n$ 个点的凸包内部找到一个嵌套的多面体。在随机生成的凸包上进行测试，并计算独立集的平均分数大小。将此结果与定理 7.10.1 中确定的常数 $c = 1/18$ 进行比较，并尝试解释任何差异。
平面-多面体距离 Plane-polyhedron distance。设计一个算法来确定一个具有 $n$ 个顶点的任意多面体 $P$ 和一个查询平面 $\pi$ 之间的距离。将距离定义为 $$ \min_{x, y} \{ |x - y| : x \in P, y \in \pi \} $$ 其中 $x$ 和 $y$ 是点。尝试在预处理后实现 $O(\log n)$ 的查询时间复杂度。与练习 7.9.2[3] 进行比较。
指状多面体的探测(Skiena 1992) Finger probing a polytope。开发一个算法，用一条穿过原点的有向直线 $L$ 来“探测”包含原点的多面体 $P$。每次探测应返回 $P$ 上被从无穷远处向内移动的 $L$ 击中的第一个面。尝试通过利用第 6 章中讨论的极对偶(练习 6.5.3[3])，来对偶变换 $P$ 和 $L$，从而实现 $O(\log n)$ 的查询时间复杂度。
外切层次结构 Circumscribed hierarchies。
1. 定义一个 $O(\log n)$ 的多边形层次结构，该结构围绕着一个凸多边形，并具有与内层次结构相似的性质。
2. 定义一个 $O(\log n)$ 多面体层次结构，该结构围绕给定的多面体。
3. 为这些外层次结构找到一些应用场景。

7.10 多面体极值点查询(Extremal Polytope Queries)