3.9 附加练习
(Additional Exercises)

3.9.1 多边形凸包(Polygon Hull)

单调多边形的凸包Hull ofmonotone polygon。开发一种算法，在线性时间内找到单调多边形的凸包。
[difficult] 多边形的凸包Hull of polygon。设计一个算法，在线性时间内找到任意多边形的凸包。注意，3.6 节中的下界适用于无序点集，并不适用于多边形的顶点。这相当棘手，一些已发表的算法后来都被发现存在缺陷。

3.9.2 正交多边形(Orthogonal Polygons)

正交凸多边形:特征描述Orthogonally convex polygons: characterization。凸多边形的标准定义是，多边形 $P$ 中任意两点之间的线段完全位于 $P$ 内部，参见 3.1 节。该定义等价于，$P$ 与任意(无限长)的直线 $L$ 的交点至多只有一个连通分支，要么是空集，要么是线段，要么是一个点。唯一真正凸正交多边形是矩形。但我们可以自然地推广凸的第二个定义，从而将"正交凸"的定义扩展到包含矩形以外的更多图形。
如果一个正交多边形，与任何垂直或水平线的交线至多只有一个连通分支，那么它就被称为正交凸多边形othogonally convex。描述正交凸多边形的形状。所谓"描述形状(characterize the shape)"是指，陈述并证明类似这样的结论: "一个正交多边形是正交凸多边形当且仅当任意两个凸顶点之间至少有一个反射顶点(reflex vertex)，并且存在一条垂直边的长度等于所有水平边长度之和的平方根。" 该命题显然是错误的，但它包含了特征描述的构成要素。当然，正交凸的定义本身就提供了一种描述: "它与任何垂直或水平线的交线要么是空集，要么是一条线段。" 但还有其他方法可以描述形状，其中一些方法将在下一个练习中有所帮助。
正交凸多边形：测试算法Orthogonal convex polygons: test algorithm。根据上面的特征描述，设计一个算法来测试给定的正交多边形是否是正交凸的。论证其正确性，可以引用你的描述，并分析其时间复杂度。

正交凸多边形的凸包Orthogonal convex hull。设 $P$ 为正交多边形。我们将其正交凸包 $\bar{\mathcal{H}}(P)$ 定义为包含 $P$ 的最小正交凸多边形。正交凸的定义见上文[1]。如果 $P$ 本身就是正交凸多边形，那么 $\bar{\mathcal{H}}(P) = P$。否则，$\bar{\mathcal{H}}(P)$ 包含 $P$。在图 3.14 的示例中，$P$ 用深色线条表示，$\bar{\mathcal{H}}(P)$用阴影表示。
设计一个算法来计算 $\bar{\mathcal{H}}(P)$。假设输入是 $P$ 的顶点坐标列表，并按照逆时针方向排列。输出一个类似的列表记录 $\bar{\mathcal{H}}(P)$ 的顶点。不要假设没有两条边位于同一条垂直或水平线上。事实上，大多数生成正交多边形的应用程序都是从整数网格中选择顶点，并且很可能有几个顶点位于同一条网格线上(如图 3.14 所示)。
至少在一个 nontrivial 的例子上手动推演一遍你的算法。
正交星形多边形：特征描述Orthogonal star polygons: characterization。如果多边形 $P$ 中存在一点 $x \in P$，使得该点能够看到多边形 $P$ 内的所有点，则称多边形 $P$ 为星形多边形(练习 1.1.4[5])。视线不必是垂直或水平的，可以是任意角度的。描述(陈述并证明)正交星形多边形的形状，是由水平边和垂直边构成的。
正交星形内核：算法Orthogonal star kernels: algorithm。星形多边形的核是指所有能够看到多边形内每个点的点的集合。设计一个算法来构造正交星形多边形的核。论证其正确性，可以引入你对多边形特征的描述，并分析其时间复杂度。
Krasnosselsky定理Krasnosselsky's theorem。描述(陈述并证明)一个正交多边形 $P$ 的形状，使得以下条件成立: 对于 $P$ 的边界上的任意两点 $a,b$，都存在一点 $x \in P$，可以同时看到 $a,b$。注意 $x$ 可能与 $a,b$ 相关。

3.9.3 关于凸包的其它问题(Miscellaneous Hull-Related)

凸多边形之间的距离Distance between convex polygons。设 $A$ 和 $B$ 为两个凸多边形，我们定义两个距离概念如下： $$ \delta = \min_{x \in A, y \in B} | x - y | $$ $$ \Delta = \max_{x \in A, y \in B} | x - y | $$ 其中 $| x - y |$ 是点 $x$ 和 $y$ 之间的欧氏距离。设计算法来计算 $\delta$ 和 $\Delta$。您可以假设 $A \cap B = \emptyset$。
首先，建立一些几何引理来确定能够达到最小或最大距离的点的类型。这些点能否位于 $A$ 或 $B$ 的内部，还是必须在边界上？如果是后者，那么这两个点是否必须是一个或两个顶点，或者说，它们能否位于某条边的内部？对于这两种距离度量，这些问题的答案不一定相同。
试着将 $\Delta$ 的时间复杂度控制在 $O(n)$，$\delta$ 的时间复杂度控制在 $O(\log n)$ 。前者并不难，但后者却相当棘手(Edelsbrunner 1985)，这需要在线性时间内找到 $n$ 个数的中位数。令人惊讶的是，计算 $\delta$ 的时间复杂度竟然小于线性时间复杂度。

凸亏树Convex deficiency tree。设 $P$ 为一个多边形(无孔)，$\mathcal{H}(P)$ 为其凸包，通常情况下，它们都被视为平面上的闭区域。定义 $P$ 的凸亏(convex deficiency) $D(P)$ 为凸包与多边形之间的差集 $\mathcal{H}(P) \ P$。一般来说，这个集合会有若干个不连通的部分，我称之为"口袋pockets"。每个口袋的形状都是一个多边形，如图 3.15(b) 所示。严格来说，这些是部分"开放"的集合，因为它们的部分边界被减去了。为了消除这个小瑕疵，我们重新定义 $D$，通过取闭包closure来填充边界。设 $\bar{Q}$ 为 $Q$ 的闭包，那么: $$ D(P) = \overline{\mathcal{H}(P) \ P} $$ 定义多边形 $P$ 的亏树(deficiency tree) $T(P)$ 如下。$T$ 的根节点与 $P$ 关联。根节点的子节点是 $D(P)$ 中不同连通部分。一般而言，如果 $P'$ 是与 $T$ 中某个节点关联的点集，那么该节点的子节点就对应于 $D(P')$ 的不同连通部分。定义 $\mathrm{P}(N)$ 为节点 $N$ 的父节点，按通常方式定义 $T$ 中节点的深度：根节点的深度为 0，任何节点 $N$ 的深度都比 $\mathrm{P}(N)$ 的大 1。
这些练习要求你探索凸亏损树的性质。
1. $T(P)$ 实际上是一棵树吗？对于多边形 $P$，它总是有限的吗？如果允许 $P$ 具有曲线边呢？
2. 让我们先定义一个节点及其关联的区域，这样诸如"节点的面积"之类的表述才有意义。节点 $N$ 的面积是否总是小于或等于其父节点 $\mathrm{P}(N)$ 的面积？节点 $N$ 的所有子节点的面积之和是否小于或等于节点 $N$ 的面积？
3. 节点 $N$ 与其父节点 $\mathrm{P}(N)$ 的顶点数量是否存在某种关系？或者 $N$ 与其所有子节点的顶点数之和，是否存在某种关系？
4. 对于一个有 $n$ 个顶点的多边形 $P$，其宽度breadth $T(P)$ 最大可能是多少？写成 $n$ 的表达式。可能得最大深度呢？请分别给出最坏情况的示例。
5. 你能用一个方程来表示，根节点所代表的点集，与它的所有后代节点的关系吗？Using set unions and difference of regions？Using sums and difference of areas？
6. 两个具有相同亏树的多边形，将他们视为组合对象，不考虑与每个节点关联的特定区域，是否必然具有相似的形状？你能找到具有相同亏树，但形状截然不同的多边形吗？这并不是一个精确的问题，因为"形状"有点主观因素。因此，请将"形状"替换为"顶点数"重新提问，两个具有相同亏树的多边形是否必须具有相同的顶点数？具有相同亏树的多边形是否存在共同特征？
7. 每棵树都可以实现为某个多边形的凸亏树吗？给定任意一棵树，如何构造一个代表性的"实现"多边形，即凸亏树为给定树的多边形？
8. 亏树的概念可以扩展到带孔的多边形上吗？
9. 亏树的概念对三维多面体有意义吗？它是树吗？它是有限的吗？
直径和宽度Diameter and width。点集 $\{p_0, p_1, \dots\}$ 的直径为，该集合中任意两点之间的最大距离$\max_{i,j} |p_i - p_j|$。
1. 证明集合的直径由凸包上两个顶点构成。
2. 集合的支撑线line of support是凸包的一条切线，并且所有点都在 $L$ 的一侧或者 $L$ 上。证明集合的直径等于该集合平行支撑线之间的最大距离。
3. 如果两个点 $a$ 和 $b$ 存在平行的支撑线，则称它们为对趾点antipodal。分别有两条相互平行的直线经过 $a,b$。设计一个算法，枚举出二维点集的所有对趾点对。将支撑线视为卡尺的钳口或许会有所帮助，可以想象着有一把卡尺围绕着点集旋转。
4. 将宽度定义为平行支撑线之间的最小距离。设计一个算法来计算二维空间点集的宽度。

洋葱剥皮Onion peeling。从平面上的有限点集 $S = S_0$ 开始迭代: 令 $S_1$ 为集合 $S_0 \setminus \partial \mathcal{H}(S_0)$ 即，$S$ 减去其凸包边界上的所有点。类似地，定义 $S_{i+1} = S_i \setminus \partial \mathcal{H}(S_i)$。持续迭代，直到空集。凸包 $H_i = \partial \mathcal{H}(S_i)$ 被称为集合的层layers，剥去这些层的过程称为洋葱剥皮。如图 3.16 所示。$H_i$ 上的任何点都被为具有洋葱深度onion depth，或简称深度depth $i$。因此，原始集合凸包上的点的深度为 0。
1. 对于每个 $n$，确定任意有 $n$ 个点的二维空间点集的最大层数。
2. 对于多边形 $P$，其深度序列depth sequence被定义为，沿边界逆时针遍历其顶点的洋葱深度序列，这是一个整数列表。对深度序列的形式，描述一些总体约束 Express some gross constraints on the form of a depth sequence.
3. 满足约束条件的每个序列是否都能用某个多边形实现？如果不能，请找出无法实现的序列。如果可以，请给出理由。

3.9 附加练习(Additional Exercises)

3.9.1 多边形凸包(Polygon Hull)

3.9.2 正交多边形(Orthogonal Polygons)

3.9.3 关于凸包的其它问题(Miscellaneous Hull-Related)

3.9 附加练习
(Additional Exercises)