5. 分治法求最近点对
步骤一：找一条中垂线 m(坐位 S 集合 x 坐标的中位数)把 n 个元素分成左右
两部分元素，步骤二：递归查找两边点集的的最短距离 d1,d2，然后取两者
中的最小者记为 d；
步骤三：在中线两边分别取 d 的距离，记录该距离范围内点的个数，中线左
边有 L 个元素，右边有 R 个元素，分别将两边的点按 y 坐标升序排列，在左
边集合中每一个点，找右边集合的点，找到与之距离小于 d 的点，更新最短
距离，直到循环结束，即可求出最短距离。
时间复杂度是：O（nlgn）
6. 格雷厄姆 Graham 扫描法求凸包
基本思想：通过设置一个关于候选点的堆栈 s 来解决凸包问题。
操作：输入集合 Q 中的每一个点都被压入栈一次，非 CH（Q）(表示 Q 的凸
包)中的顶点的点最终将被弹出堆栈，当算法终止时，堆栈 S 中仅包含 CH(Q)中
的顶点，其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。
具体步骤如下：
（1）设 P0 是 Q 中 Y 坐标最小的点，如果有多个这样的点则取最左边的点作
为 P0；
（2）设<P1,P2,……,Pm>是 Q 中剩余的点，对其按逆时针方向相对 P0 的极角
进行排序，如果有数个点有相同的极角，则去掉其余的点，只留下一个与 P0
距离最远的那个点；
（3）PUSH(p0 , S)
（4）PUSH(p1 , S)
（6）PUSH(p3 , S)
（7）for i ← 3 to m
{
while 由点 NEXT-TOP-TOP（S），TOP（S）和 Pi 所形成的角形成一次
非左转
do POP(S)
PUSH(pi , S)
}
（8）return S
时间复杂度是：O（nlgn）
注：Jarvis 步进法更加容易理解，见算法导论中文版 P609。
7. D&C for 2D maxima Finding Problem
（1）如果点集 S 只包含一个点，这直接输出该点。否则找一条中垂线 m(坐位 S
集合 x 坐
标的中位数)把 n 个元素分成左右两部分个数相等的元素，分别为 Sl 和 Sr。
（2）递归查找两边点集的的最大点；
（3）将获得的所有最大点按 y 值排序，并查找出 Sl 中 y 值小于 Sr 中最大点的
y 值的最大点，并将其排除；
（4）最终获得所有的点集 S 的所有 maximal point。
时间复杂度是：O（nlgn）
3
