编辑“︁点集最近点对”︁（章节）

== 分治法优化 ==  
分治法可将时间复杂度优化至<math>O(n \log n)</math>，步骤如下：  
1. '''按x坐标排序'''点集并递归分割为左右两半。  
2. '''递归求解'''左右两半的最近点对。  
3. '''合并阶段'''：检查距离分割线小于当前最小距离的点，构成候选点对。  

=== 算法细节 ===  
* '''分割线'''：取点集的中位数x坐标。  
* '''候选区域'''：仅需检查距离分割线<math>d</math>（当前最小距离）以内的点。  
* '''纵坐标优化'''：在候选区域内按y坐标排序，只需检查后续7个点。  

=== 代码示例 ===  
<syntaxhighlight lang="python">  
def closest_pair(points):  
    points_sorted_x = sorted(points, key=lambda x: x[0])  
    return _closest_pair(points_sorted_x)  

def _closest_pair(points):  
    n = len(points)  
    if n <= 3:  
        return brute_force_closest_pair(points)  

    mid = n // 2  
    left_pair, left_dist = _closest_pair(points[:mid])  
    right_pair, right_dist = _closest_pair(points[mid:])  
    min_dist = min(left_dist, right_dist)  
    min_pair = left_pair if left_dist < right_dist else right_pair  

    # 合并阶段  
    mid_x = points[mid][0]  
    candidates = [p for p in points if abs(p[0] - mid_x) < min_dist]  
    candidates.sort(key=lambda x: x[1])  

    for i in range(len(candidates)):  
        for j in range(i + 1, min(i + 8, len(candidates))):  
            dist = math.sqrt((candidates[i][0] - candidates[j][0])**2 + (candidates[i][1] - candidates[j][1])**2)  
            if dist < min_dist:  
                min_dist = dist  
                min_pair = (candidates[i], candidates[j])  
    return min_pair, min_dist  
</syntaxhighlight>  

=== 复杂度分析 ===  
* 时间复杂度：<math>O(n \log n)</math>（排序占主导）。  
* 空间复杂度：<math>O(n)</math>（递归栈和临时数组）。