8.7 可分离性
(Separability)

机器人技术(特别是机械装配)、电路布局以及图形学领域的诸多应用，推动了对各种"可分离性(separability)"问题的研究。这类问题的关注，如何在不发生碰撞的情况下将物体彼此分离。 该问题的一个典型场景是搬家工人清空房屋内的物品。给定平面上的一组互不相交的多边形，是否可以将其中每一个多边形移动到无穷远处而不干扰其他多边形? 当然，这种运动必须是平面内的连续运动。避障的概念与机器人运动规划问题中使用的概念相同: 若两个多边形共用一个内部点，则视为发生碰撞。 所谓移动到无穷远，是指移动到任意远的地方。通常会对允许的运动类型施加一定的限制，例如仅限平移。后文中将看到，指明每次只能移动一个多边形还是可以同时移动多个多边形也很重要。 在本节中，我们仅对此领域做简要的介绍，以展示其丰富的内容。

8.7.1. 可分离性的种类 (Varieties of Separability)

即使对允许的运动没有限制，也并非所有的多边形集合都是可分离的。如图 8.27(a) 显示了两个互锁的多边形，它们是不可分离的，除非将其中一个提升到三维空间中。 有些多边形集合如果允许旋转是可分离的，但如果仅通过平移则是不可分离的，就像图 8.27(b) 中的那对多边形。

如果每次只能移动一个多边形，而其他多边形保持静止，那么一组多边形可能是可分离的，但需要大量的移动步骤。 如图 8.28 所示，通过交替向右移动 \(A, B\)，可以使该构型分离，从而释放 \(Q\) 使其能够向右上方移动。但是，将 A 和 B 移出的移动次数取决于间隙 \(\delta\) 与长度 \(L\) 的比例。 移动次数至少为 \(L/ \delta\)，这可以随意变大，且与顶点数 \(n\) 无关。

这个例子似乎并不能说明该问题真的很难。如果可以同时移动两个多边形，分离这组多边形就很容易。即使每次只移动一个，也没有哪个多边形必须移动"很长(large)"的总距离， 这里的长是相对于原始构型凸包的直径而言的。尽管如此，我们将看到，在这些意义上可分离性问题确实是"困难"的。

关于可分离性的最早，或许也是最漂亮的工作是由 Guibas & Yao (1983) 做出的。他们证明了一组凸多边形可以在以下运动条件下被分离:

1. 平移(Translation): 所有运动都是平移。
2. 单向(Unidirectional): 所有平移都在同一个(任意)方向上。
3. 移动一次(Moved once): 每个多边形只移动一次。
4. 一次一个(One-at-a-time): 每次只移动一个多边形。

这些都是严格的限制，许多原本可分离的多边形在这些限制下变得不可分离。例如，图 8.29 中的一对多边形沿方向 \(u\) 是不可分离的。 然而，在这些条件下，凸多边形(或者说是凸曲面形状)可以沿任何方向分离。如果读者觉得这在直觉上显而易见， 那么了解到三维空间中的凸物体在这些条件下并不总是可分离的，可能会感到震惊(练习 8.7.5[1])。

应用(Application)

Guibas & Yao(1983) 的研究工作源于当时工作站上出现的一项新技术 —— 窗口系统。某些工作站配备了硬件指令，可以将一块屏幕内存区域的内容复制到另一个位置。 若要利用这条指令移动多个窗口而不发生内存覆盖，可以通过根据某种可分离性顺序(separability ordering)依次移动各个窗口来解决。

分离线段 (Separating Segments)

我们从一个特殊情况开始，稍后我们将看到这种情况足以涵盖一般情况，即，分离一组互不相交的线段。不妨设线段要在正 \(x\) 方向上分离，这种假设不失一般性。 显然，如果我们能在当前集合中，找到出一条可以水平向右移动，而且不与任何其他线段碰撞的线段，那么这些线段沿该方向就是可分离的。 因为当我们把该线段移到无穷远后，我们就得到了一个规模更小的相同问题，我们可以继续识别下一条可以移动的线段，如此往复。

试想从 \(x = +\infty\) 处照射这些线段，如图 8.30 所示。此时问题便转化为: 是否总能找到一条完全被照亮的线段？

分离凸多边形 (Separating Convex Polygons)

针对凸多边形的分离问题，可以通过一个简单的现象来解决。一个凸形状 \(C\) 水平移动时，其右边界扫过的区域，是该形状 \(C\) 最左侧最高点与最低点之间的线段 \(s\) 扫过区域的子集(见图 8.31)。 因此，对于一组凸形状，只要有一个能够在垂直方向上分离这些线段的调度方案，就足以分离这些形状本身。

复杂度(Complexity)

计算一组凸形状的分离顺序，类似于沿分离方向对它们进行排序，因此，该过程可以在 \(O(n \log n)\) 时间内完成。在此我们不证明 Guibas & Yao (1983) 的这一结论了。

8.7.3. 基于划分问题的归约 (Reduction from Partition)

在考虑了一个简单的可分离性问题的例子之后，我们将在本节及下一小节中证明，一般意义上的可分离性问题在某种程度上是"困难"的。 问题的困难性可以通过建立其计算复杂度的下界来体现。可以参考第 3 章(3.9节)中的套路， 从一个已知的困难问题归约到该问题上。其核心思想是证明: 如果能快速求解问题 \(B\)，那么我们也能快速解决某个已知困难的问题 \(A\)。 这就确立了 \(B\) 至少和 \(A\) 一样困难，即，\(A\) 被归约 reduced 到了 \(B\)。

我们研究的分离问题 \(B\) 只允许平移，且每次只能移动一个多边形。但每次平移可以在不同的方向上进行，且每个多边形可以被移动多次。 作为参照的已知困难问题 \(A\) 是划分问题(partition problem): 给定一个整数集合 \(S\)，判断是否可以将其划分为两个部分，使得这两部分的元素之和相等。 例如，\(S = \{1, 3, 3, 5, 6\}\) 是可以划分的，因为 \(1 + 3 + 5 = 3 + 6\)，但集合 \(\{1, 3, 3, 5, 10\}\) 是不可划分的。 虽然这看起来可能不是一个非常困难的问题，但至今无人找到一种求解方法，其效率显著优于穷举 \(S\) 的所有可能划分。 由于包含 \(n\) 个元素的集合有 \(2^n\) 种可能的划分，穷举是一个非常缓慢的算法，它需要关于 \(n\) 的指数时间，因此对于 \(n \ge 100\) 的情况实际上是无用的。 此外，划分问题已被证明是NP完全, NP-complete的，这意味着它属于一类看似难以有效求解的问题。

给定划分问题的任何实例，我们构建一个相应的可分离性问题，该可分离性问题可解当且仅当原划分问题可解。图 8.32 针对集合 \(\{1, 3, 3, 5, 6\}\) 说明了这种构造。 它由若干高度为 1、宽度对应于 \(S\) 中各元素的方块组成。设 \(\Sigma\) 为 \(S\) 中所有数字之和。图中的部件 \(Q\) 可以向下和向右移动， 当且仅当这些方块可以被装入左侧 \(((\Sigma/2) \times 2)\) 的空存储矩形空间内。而这能实现的前提是集合 \(S\) 能够被划分为两个总和相等的子集。

这证明了该版本的分离问题至少与划分问题一样困难——用专业术语来说，分离问题是NP难, NP-hard的。

8.7.4. 模拟汉诺塔 (Mimicking the Towers of Hanoi)

尽管我们已经证明了分离问题是困难的，但值得注意的是，分离这种特定的构型并不需要大量的移动操作。虽然这可能需要大量的离线分析，但一旦知道了具体的移动步骤，实际操作是很容易完成的。 只需将每个构件(块)移动一次即可。最后，我们来看一个例子，其解法不难找到，但其中某些构建需要移动指数级的次数。同样，我们限制移动方式仅为平移，并允许多边形移动多次，但每次始终只能移动一个。

该例子基于著名的"汉诺塔"谜题。在这个谜题中，不同半径的圆盘堆叠在三根柱子中的一根上，按大小排序，最大的在底部，最小的在顶部，如图 8.33 所示。 任务是将圆盘逐个从柱子 \(A\) 移动到柱子 \(B\)，必要时刻意使用柱子 \(C\)，使得在任何时候至多只有一个圆盘处于空中，即不在柱子上，并且任何圆盘都不能放置在半径更小的圆盘上。 这种始终保持有序的条件导致了大量的移动操作，将 \(n\) 个圆盘从 \(A\) 移动到 \(B\) 需要 \(2^n - 1\) 次移动(Rawlins 1992, p.14–26)。

Chazelle et al.(1984) 提出了一个模拟汉诺塔谜题的巧妙分离实例。该实例用 \(n\) 个 U 形多边形模拟圆盘，每个多边形的高度为 \(h\)，厚度为 1，它们可以紧密地相互嵌套在一起， 形成一个高度为 \(n + h\) 的堆栈，如图 8.34(a) 所示。任何未按大小排序的堆栈高度必须至少为 \(n + 2h\)，如图 (b) 所示。通过选择远大于 \(n\) 的 \(h\)，我们可以确保有序堆栈比无序堆栈紧凑得多。

该分离谜题如图 8.35 所示。标记为 \(A, B, C\) 的三个矩形槽对应三根柱子。只有当 \(A\) 为空时，多边形 \(Q\) 才能向右和向下滑动。 \(A\) 只能通过将 \(n\) 个 U 形多边形移入槽 \(B\) 和 \(C\) 来清空。由于无序堆叠的低效性，这只能通过近乎模仿汉诺塔移动的方式来完成， 之所以说是"近乎"，是因为每列允许出现一次违反排序规则的情况，但不能超过一次。因此在 \(Q\) 被分离之前，每个 U 形多边形仍然需要指数级的移动次数。

8.7.5. 练习

1. 三维分离 Separating in three dimensions。在三维空间中找出一组凸多面体，使它们在某个方向上无法按照 Guibas & Yao(1983) 的方法进行分离。
2. 分离球体 Separating sphers。证明或反驳以下命题: 三维空间中一组互不相交的球体，可以通过平行于任意给定方向的平移，将他们逐个分离出来。
3. 非不相交线段 Nondisjoint segments。引理 8.7.1 能否推广到如下类型的非不相交线段? 一组内部互不相交，但可能存在接触情况，即某线段的端点位于另一个线段上。 线段的内部是指去掉端点后的部分。多边形的边就是此类情况的一个特例。
4. 下界 Lower bound。证明计算一组互不相交线段分离顺序的算法复杂度下界是 \(\Omega(n \log n)\)。
5. 划分 Partition。加强划分归约的结论，使其适用于每个部件仅允许进行单次平移的情况。
6. 改进汉诺塔 Hanoi improvements。
   1. 分离图 8.35 中的多边形构型究竟需要多少次移动? 此处将"移动"定义为任一个部件的连续平移，不一定沿直线。
   2. 证明图 8.35 中的谜题(对于一般情况 \(n\)) 需要指数级的移动次数。具体方法是证明所需移动次数存在指数级下界。
   3. 修改谜题的结构，使得移动更贴近汉诺塔的移动方式，从而要求至少需要 \(2^n - 1\) 次移动，才能将 \(n\) 个 U 形块从区域 \(A\) 移出。
   4. 能否修改谜题，使得即使允许同时移动任意数量的多边形，仍然需要指数级的移动次数?
7. 星形多边形 (Toussaint 1985b) Star polygons。回顾第 1 章(练习 1.1.4[5]) 中关于星形多边形的定义，即从其内部某一点可见的多边形。
   1. 是否总存在某个方向的单次平移，能将两个星形多边形分开? 若否，给出反例。若是，给出证明。
   2. 针对三个星形多边形, 回答 (a) 中的问题。
8. 单调多边形 (Toussaint 1985b) Monotone polygons。回顾第 2 章(2.1节) 的内容， 严格单调多边形是指其边界与任何平行于某方向 \(u\) 的直线相交时，交点不超过两个的多边形。
   1. 证明两个严格单调多边形(可能关于不同方向单调)总是可以通过单次平移分离的。
   2. 设计一个算法来寻找能将它们分离的方向。
   3. 如果多边形是单调的但非严格单调的，即如果多边形边界与任何平行于某方向的直线相交时，交集由至多两个连通集构成，这些集合可以是线段，你的结果会有变化吗？