目标：对一系列的几何体，判断它们是否有交集，计算它们交集的个数，枚举所有的交集，构建这些交。
1、Preliminary

  • EU问题

问题描述：给定一系列的实数，判断是否互异。

算法：将他们排序，然后可以通过线性扫描找到。复杂度O(nlogn)

  • Minimum Gap：对于实轴上的n个点，找到相邻两个的最小距离

对于这个问题，我们可以利用EU问题来规约，两个问题的输入都是n个整数，Minimum Gap如果是正数，那么EU的输出为Yes，如果是0，EU的输出是No。因此Minimum Gap的下界也是O(nlogn)

  • Maximum Gap：

算法描述：先找到最小值lo,和最大值hi，然后将这段分成n-1段，然后对每一个元素进行整除放进桶里。接着做线性扫描，先除去那些空桶。对于前面的桶考虑最右元素和后面桶的最左元素。考虑这两者然后找到最大的缝隙。

  • Integer Element Uniqueness：EU问题中的元素全都为整数

2、Interval Intersection Detection：区间交问题
问题描述：给定一系列数轴上的区间，判断它们是否有交

简单算法：将他们按照顺序排列，左端点标记为L，右端点标记为R。如果存在LL或RR的pattern，那么则存在交。

规约：将IEU问题规约到IID

IEU的输入是一系列整数，那么将这些整数输入变成(x,x+0.5)，那么就变成了IID的输入；

而IID的输出如果有相交，说明IEU内有重复元素，反之亦然。

3、Segment Intersection Reporting

现在考虑平面上的n条线段，判断他们是否有交点。

有个简单的方法就是枚举所有的线段对，那么则是O(n^2)的时间，具体求交可以用4次ToLeft测试。然而我们可以找到一个O(nlogn +I)的时间的算法，I是所有交点的数目。

规约：证明SID至少需要O(nlogn)时间

我们可以将EU问题规约到SID问题

EU问题的输入是一系列的点，将这些线向上拔高变成n条线段，那么就可以变成SID问题的输入。那么这样一组线段没有交当且仅当EU问题中没有重复元素。

4、BO Algorithm

问题描述：找到平面上所有线段相互之间的交点。

定理：两条线段有交点当且仅当这两条线段可以在一条垂线上紧邻

  • 算法分析：

对于平面上的线段，当垂线扫描过平面时，这些线段与垂线的交点由高到低有一个序列

这些序列会在以下三种情况发生变化：

(1)、垂线遇到左端点时，序列要增加一个点

(2)、垂线遇到右端点时，序列要减少一个点

(3)、序列遇到交点后，那两条线段与垂线的交点要交换次序

  • 数据结构

(1)、Status Structure：记录当前时刻垂线上所有点的序列

(2)、Event Queue：上述三种会改变点序列的情况的称为event，将这些events构成一个优先级队列

具体操作：

①、当遇到左端点时

将该左端点插入到Status 序列上，并且判断这条线与它的前驱和后继是否会发生相交。如果会，将相交事件插入到Events队列中。

②、当遇到右端点时

将该右端点从Status序列中删除，并判断它的前驱与后继是否会发生相交。如果会，将相交事件插入到Events序列中。

③、如果遇到交点
交换两条线在垂线上的交点序列，然后交换后分别判断它们与新的前驱和后继是否会发生相交，若相交，同样的也是将相交事件加入到Events队列中。

另：对于如下的那些退化问题，我们在这里不予考虑

  • 细节补充

对于Events队列的初始化，我们将左端点和右端点按照次序分别放入优先级队列中。

在算法运行过程中，我们会根据上面提到的三种情况动态的插入一些相交事件。因此优先级队列的操作可满足该算法的需求。

至于Status 序列，我们使用平衡二叉搜索树即可实现。操作有插入、删除、查看前驱、查看后继。

  • BO 分析

BO算法正确性：因为两条线段有交点当且仅当它们在相交前必然会处于紧邻状态。因此不会漏掉交点。

算法复杂度：

根据之前数据结构的了解，我们在这些单独的数据结构里消耗的时间总体不会超过O(logS)，这里的S指的是size of data structure.

Events 队列的消耗时间：2n+I，I指的是交点的数目。I最大可达n^2

//然而因为我们前面有log，因此即使是log(2n+n^2)，最后也是一个Logn的阶。对于老师讲解的这句话存疑…

而一开始我们初始化放进2n个点的时候，我们可以用O(n)的时间来构造优先级队列

Status sequence消耗的时间：在任何一个时刻，与垂线相交的线不会超过n条。因此我们对status的操作单次最高不会超过logn

因此最后总体的时间不会超过O((2n+I)*logn) = O((n+I)*logn)的时间。空间复杂度是O(n+I)。

理论上在最坏情况下I可能会达到n^2，那么此时比蛮力算法O(n^2)还要糟糕，但是一般情况下不会出现这种情况，因此在大多数情况下BO算法已经够用。

5、Detecting Intersection Between Convex Polygons
问题描述：这节的问题是判断两个凸多边形是否有交，以及有交的话找出它们的公共边。在这里我们规定一个凸多边形完全包含于另一个凸多边形的时候也判作是交。

  • Dobkin and Kirkpatrick’s algorithm

首先将一个凸多边形以它的最上面的点和最下面的点做水平射线，并分为两部分。

然后对于两个凸多边形而言，如下图，如果它们有交当且仅当一个凸多边形红色的两条射线必与另一个凸多边形的两条红射线有交，蓝的亦是如此。

算法：每次找到一侧多边链的中间的那条边，减而治之，利用递归。

递归基：当有一侧的链数小于2时，递归结束

中间情况：

(1)、找到交点，此时算法结束

(2)、可删去一侧链的一半边

如图可知，如果两个凸多边形有交，必然不会发生在黄色区域。而蓝色边是链的中间边，所以可以一侧可删去一半的规模。//（完了这里我也不知道为啥可以去除黄色部分）

(3)、可删去两个侧链的各一半边

如图亦是如此，如果有交，必然不会发生在黄色区域。此时两边各删去了一半规模

  • 算法复杂性：因为每次至少能减去一侧链的一半，因此递归的复杂度为

T(n) = T(3n/4) +O(1)

T(1)= O(1)

最终T(n) = O(logn) 类似于二分查找。

6、探讨如何求出两个凸多边形的交。

  • O’Rourke’s Algorithm（边追赶算法）

如图所示，首先一开始先确定初始两个凸多边形各一条边，然后判断谁先开始往哪个方向，如果移动后与另一凸多边形的选定的边有交点，那么就移动另一多边形的那条边也直至与其有交点。交错进行。

算法复杂度：相当于是merging两个序列，每次判断是O(1)的时间，遍历了两个凸多边形的边，因此最后是O(n+m)的时间。

  • Plane Sweeping 算法

用一条扫描线自左而右地扫描构造

这里的数据结构可以很简单，因为扫描线上的点最多只会有4个。

而Events队列中有效事件只有两个凸多边形的最左侧的点，当我们检测到垂线有四个点时，就去检测这四条边的endpoint是否是交点即可。

复杂度：红色交点不超过n+m，而每一次操作都是常数，那么最后的复杂度就是O(n+m)

7、Halfplane Intersection Construction
广义凸多边形：凸多边形缺了边，可以假想在无限远处有剩余的边连接。

现在对于一系列的半平面，找出它们的公共交集。

HIC的复杂度，不可能低于nlogn。

规约：

sorting输入：分布在轴上的点，对于x轴上的点t，找到y轴上的1/t，连接这两条边。此时将一系列的点转换成了一系列的直线。然后将每一条直线划分出来的半平面保留上面的那个半平面。因此转换成了HIC的输入，这里花费的时间不超过线性。

HIC输入：一系列的半平面

假设算出了HIC公共的交，可以通过遍历转换回sorting是输出

算法：将半平面集尽可能的均匀分成两个子集H1和H2，然后递归的构造出H1公共的交凸多边形C1，以及H2公共的交的凸多边形C2。不管是C1还是C2都有可能是无界的凸多边形。然后对C1和C2进行求交，然后就得到了它们的半平面交。

复杂度：T(n) = 2*T(n/2)+O(n), T(n) = O(nlogn)