平面几何的并行算法

(并行与分布式计算五)

computational geometry: design efficient algorithms to handle computational problems dealing with collections of objects in Euclidean space

three technique:

divide-and-conquer 分治
plane-sweep tree 平面扫描树
pipelined divide-and-conquer

凸包(Convex-Hull)计算

欧几里得空间中两点p_1 = (x_1, y_1)和p_2 = (x_2, y_2)
s = $p_1p_2$定义为满足$q = ap_1 + (1-a)p_2$(0 <= a <= 1)的q点的集合
s consists of all the points lying on the straight-line segment joining $p_1$ and $p_2$， including $p_1$ and $p_2$

称p_1和p_2为s端点

凸包(CH(S))可以按上凸包(upper hull UH(S))和下凸包(lower hull LH(S))两部分来分别算

设p和q分别是输入的点集S中x坐标最小和最大的点，则凸包被p和q两点分割成两部分，分别是上凸包和下凸包

上凸包是从p顺时针到q的凸包子列
下凸包是从q顺时针到p的凸包子列

凸包计算(串行算法)

为了串行地算凸包，把输入点集用线段pq分成上、下两部分，上部分用来算上凸包，下部分用来算下凸包

为了计算上凸包，对上部分的点集进行关于x坐标的排序，然后按x坐标从小到大逐点扫描该点集：
设当前上凸包为v_1,v_2,…,v_k，则当从v_k到被扫描到的点v的线段角度比v_k-1到v_k的线段角度小时，把v作为v_k+1插入到上凸包最后面，再让k的值加1，否则的话去掉当前上凸包最后的点（k的值减1），并重新判断，如果还不行则继续让k的值减1，直到v能加入到上凸包中

下凸包的计算与上凸包的类似

上凸包计算(快速串行算法)

对上部分的点集进行关于x坐标的排序（O(n log n)复杂度）

按x坐标从小到大逐点扫描该点集(n次外迭代):

用二分法确定正在被扫描的点v究竟是上凸包中第几个点(O(log n)复杂度)
把v插入到上凸包中（O(1)复杂度）

整体复杂度为O(n log n), 意味着并行算法的W要做到O(n log n)才是optimal算法

上凸包计算(并行计算思路)

分治法:

分：把输入点集分成左、右点数基本均等的两组
治：在左、右两组中分别用分治法来计算上凸包
合：把左、右两组的上凸包合在一起

左右上凸包合并

串行算法:

外循环：用二分法搜索切线段的左端点
内循环：固定切线段的左端点，用二分法搜索切线段的右端点
复杂度：O(log^2 n)

并行算法:

并行外循环：用p+1分法搜索切线段的左端点
并行内循环：固定切线段的左端点，用p+1分法并行搜索切线段的右端点
取p=根号n
T=O(1)，W=O(n)

Algorithm 6.1

(Upper Common Tangent)
Input: The upper hulls UH(S_1) = (r_1, r_2, ..., r_s) and UH(S_2) = (q_1, q_2, ..., q_t) in sorted order from left to right, where S_1 = (p_1, p_2, ..., p_n/2) and S_2 = (p_(n/2+1), p_(n/2+2), ..., P_n) such that x(p_1) < x(p_2) < ... < x(p_n). Assume that sqrt(s) and sqrt(t) are integers. 
Output: Points u and v such that the line determined by u and v is the upper common tangent between UH(S_1) and UH(S_2).
begin
1. For each i such that 1 <= i <= sqrt(s), find q_(j(isqrt(s))) such that r_(i*sqrt(s))q_(j(i*sqrt(s))) is the tangent to UH(S_2).
2. For each i such that 1 <= i <= sqrt(s), determine whether u is to the left of, is equal to, or is to the right of r_(i*sqrt(s)). If u = r_(i*sqrt(s)), for some i, then we are done. Otherwise, deduce the block A = (r_(l*sqrt(s)+1), ..., r_((l+1)sqrt(s)-1)) containing u.
3. For each r_i in block A, determine q_(j(i)) such that r_i*q_(j(i)) is the tangent to UH(S_2), set u := r_i and v := q_(j(i)) if r_i*q_(j(i)) if r_i*q_(j(i)) is also tangent to UH(S_1).
end

上凸包计算(快速并行算法)

假设输入点集已经按x坐标排好序

分：把输入点集分成左、右点数基本均等的两组，T=O(1), W=O(n)
治：在左、右两组中分别用分治法来计算上凸包，假设$T=T{n/2}, W=2W{n/2}$
合：把左、右两组的上凸包合在一起，T=O(1), W=O(n)

总体并行复杂度：$Tn=T{n/2}+O(1)=O(log n), Wn=2W{n/2}+O(n)=O(n log n)

凸集求交(Intersections of Convex Sets)

intersection of half-planes(半平面的交)

每条直线方程L: y=ax+b都把二维平面分成两个半空间: $H^+(L)$和$H^-(L)$，分别对应y>=ax+b和y<=ax+b

多条直线，每条选一个半空间，这些半空间的交可以看作凸集的交

思路: 把凸集求交转化为凸包计算

点转换为线：T(a, b) -> y = ax + b
线转换为点：T(y = cx + d) -> (-c,d)
如果d >= -ca + b，那么b <= ca + d
如果d <= -ca + b，那么b >= ca + d

为了求出凸集的边界依次在哪些直线上，可以转为求这些直线的转换点的凸包

把凸集求交转化为凸包计算原理:

平面扫描(Plane Sweeping)树

Plane Sweep: 给定平面上的集合对象的一个集合，想象一条垂直线(竖直线)从左到右扫过平面；从扫描线的关键位置(critical points)得出某些问题的解

Plane-Sweep Tree

输入数据：s_i: (a_i, b_i)与(c_i, d_i)的连线
假设：s_i组成二维平面的分划
构建一树状数据结构，对平面上任意点都可以快速找出包含该点的分划面

模型简化:

构造过程中，线段的角度不重要，线段的上下关系才是关键
不妨去掉角度信息，只保留上下关系
所以可以把这些线段都简化为水平线，用y值来记录其相互间的上下关系

数据结构:

图中的树，叶节点是线段端点的x把二维空间垂直分割的部分，其它节点是这些部分的两两合并
节点的W是每一垂直分割部分中，至少有一个端点在该部分中，并且从该部分穿过的线段的集合
节点的H是覆盖节点的垂直分割部分但不覆盖父节点的线段集

构造平面扫描树的并行算法

引理6.5: 令T为不相交的n段水平段的集合的平面扫描树，H(v)和W(v)为每个结点v存储的链表；则$\sum_v|H(v)|$和$\sum_v|W(v)|$都为O(nlogn)
父节点的W由其子节点的W合并而成，可以用并行归并算法
除了根节点的H必然是空集外，其它节点的H必然是其父节点的W的子集
通过检验一条线段在兄弟节点的覆盖性，可以确定该线段是否在H中
通过并行前缀和算法，可以从W快速压缩得到H

并行复杂度:
T = O(logn), W = O(nlogn), a set S of n horizontal segments

可视性问题(Visibility Problems)

给定平面上由禁止曲线(forbidden curves)和点p组成的集合F，点q对p是可视的，如果线段pq和F中的任意曲线不相交
如果F由直线段组成，则对p可视的点组成多边形，称为p的可视多边形
线段集合的下包络(the lower envelope of a set of segments)
假定p点是任意一个负无穷点
p的可视多边形由集合的线段的下包络指定

并行解法:

L的计算可以用并行归并算法
在L的基础上，合并vis数组可以用T=O(1)时间
使用算法4.4的流水线归并排序算法， T = O(logn), W = O(nlogn)