025改进分治算法的途径2：增加预处理 

改进分治算法的途径2：增加预处理

例子：平面点对问题

输入: 平面点集 P 中有n 个点, n >1 输出: P中的两个点，其距离最小 蛮力算法：

C(n,2)个点对,计算最小距离，O(n2) 分治策略: P 划为大小相等的PL和PR 1. 分别计算 PL、PR中最近点对 2. 计算 PL与PR中各一个点的最近 点对

3. 上述情况下的最近点对是解 2

划分实例：n=10

PL l PR 3

算法伪码

MinDistance (P, X, Y)

输入: 点集P, X和Y为横、纵坐标数组 输出: 最近的两个点及距离

1. 若|P|?3，直接计算其最小距离 2. 排序X,Y

3. 做中垂线 l 将P划分为PL和PR 4. MinDidtance (PL,XL,YL) 5. MinDistance (PR,XR,YR)

6. ?=min(?L,?R)//?L,?R为子问题的距离 7. 检查距 l 不超过?两侧各1个点的距 离. 若小于?，修改 ?为这个值 4

跨边界处理

? d?(?/2)?(2?/3)??/4?4?/92222d 2? ?25?/36?5?/6右边每个小方格至多1个点，每个点至多比较对面的6个点，检查1个点是常数时间，O(n) 个点需要O(n)时间

5

2