Caleb's Space

Appearance

「计算几何」利用几何对偶将判断两组点是否线性可分问题转化成线性规划问题

Published at:

问题描述 ​

给定二维平面上的两组点（红点和蓝点），我们希望判断：

是否存在一条直线，能够将所有红点和蓝点完全分隔在直线的两侧？

这个问题被称为线性可分性判断问题，暴力法求解该问题需要 的时间复杂度，有没有一种办法能够在线性的时间里判断这个存在性问题呢？

几何对偶（Geometric Duality） ​

几何对偶是计算几何中一种将“点”与“线”之间关系转换的技术。本文采用一种经典的二维平面对偶变换：

  • 原空间中的点 ，在对偶空间中表示为一条线：
  • 原空间中的线 ，在对偶空间中表示为一点：

这个对偶变换具有以下性质：

  1. 保持位置关系：如果点 在直线 的上方，则对应的对偶点 在对应对偶线 的上方, 反之亦然。
  2. 点在直线上 <-> 对偶线过对偶点

这两个性质非常容易证明。

性质1的证明 ​

假设原空间中有点 在直线 上方，则有 。

在对偶空间中，比较点 和直线 的关系，即比较 与 的关系。易得： 。

证毕，反之亦然。

性质2的证明 ​

假设原空间中有点 和直线 ，点 在直线 上，则有 。

在对偶空间中，对偶直线 是否穿过对偶点 。因为 因此对偶直线穿过对偶点。推广这个结论，我们还能得到，原空间中多个点在同一条直线上，转化到对偶空间就变成了多个直线交于一点。

问题转换 ​

回到我们的问题：红蓝点是否线性可分？

我们首先讲这个问题转化到对偶空间中，这个问题变成了：

是否存在一个点 $ (x, y) $，在所有红线的下方同时在所有蓝线的上方 或者 在所有红线的上方同时在所有蓝线的下方？

为了简单，我们可以讲这个问题暂时简化为：

是否存在一个点 $ (x, y) $，在所有红线的下方，同时在所有蓝线的上方？

要求这个问题，依然有不小的难度，但是我们可以对问题进行进一步的转化，如果我们把所有的蓝线转化为向下的一个个半平面（half-plane），同时把所有的红线转化为向上的半平面。那么，这个点是否存在性问题就转化为了：

给定一系列红色半平面和蓝色半平面，请问他们有没有交集？

一但这些平面有交集，我们一定可以在其中找出一个点满足所有的红线在下方，所有的蓝线在他上方。

算法流程与时间复杂度 ​

求解半平面是否有交点问题，我们可以使用线性规划的算法。算法的流程如下：

  1. 给出一个随机的半平面排序
  2. 选取任意方向 ，设置线性规划问题的目标函数为：。 （因为这是一个可行性问题，我们不关心目标函数的最大值是多少，只关心是否存在一个点满足所有半平面约束。）
  3. 首先求出 与 的交点作为初始解（如果没有交点，直接返回无解）
  4. 从第 3 个半平面 开始，依次加入，并且判断上一步的解 是否满足新的半平面约束（即是否在 内部）；
  • 如果满足，则该点仍为当前最优解，继续处理下一个半平面；
  • 如果不满足，说明当前解不再合法：
    • 这时，新的最优解必须在 的边界上，也就是说，我们需要在 与之前所有 中使得解仍满足这些约束；所以我们将问题降维：转化为在一条直线上寻找一维最优点的问题；
    • 这就是一个1D 线性规划，可以在常数时间内解决；
    • 如果在这条边界上无法找到合法点，说明所有半平面无公共交集，直接返回“不可行”。
  1. 重复步骤 4，直到所有半平面处理完为止。如果始终能找到合法的解点，说明原问题有解，返回最终可行点作为“存在性”证明。

这个解法其实就是 Seidel 随机增量算法。

期望时间复杂度 ​

首先给出二维动态规划里的两个概念：

  • 约束集合（Constraint Set）：在我们讨论半平面可行性时，每个半平面都可以看作是一个线性不等式。把目前已经加入到线性规划里的所有不等式（即所有半平面）集合称为“约束集合”。第 i 步时，这个集合恰好有 i 条约束。

  • 基约束（Basis Constraint）：在二维线性规划里，一个“最优解”通常会落在某两条边界线（也就是两条约束）相交的点上。我们把这两条使最优解“恰好位于其交点”的约束称为“基约束”。换句话说，如果最终最优解 x* 是由约束 和 共同确定的，那么 和 就属于基约束。

当我们用随机顺序依次加入每个半平面约束时，令当前已处理的约束集合大小为 。假设在第 步时，我们已有一个可行解 。要判断加入的第 个半平面 是否破坏当前解，只需 时间：

  • 如果 依然满足 ，则第 步开销为常数。
  • 如果 不满足 ，则说明最优解一定位于 的边界上。此时我们需要在这条边界直线上重新求解一个一维线性规划（1D LP），再检查之前所有 个半平面的约束。这一步 1D LP 的时间开销是 。

下面来计算第 步所需时间的期望值。由于我们在所有 个半平面之间是随机打乱顺序，第 个插入的半平面成为最终「基约束（basis constraint）」的概率恰好是 （因为在二维中，最优解的边界最多由两条约束构成）。换句话说：

  • 以概率 ，添加第 个约束后 仍可行，只需 检查。
  • 以概率 ， 不再可行，需要花费 做一次 1D LP。

因此，第 步的 期望时间

把所有 步加起来，总期望时间为

因此，Seidel 的随机增量算法在二维半平面可行性检测问题上具有 的期望时间，这就意味着判断红蓝点线性可分的对偶方法在期望线性时间内可解。

参考资料 ​

M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed. Berlin, Germany: Springer, 2008, ISBN 978-3-540-77973-5.