js寻找最近的点对，使用分治法

在JavaScript中，如果要用分治法寻找一组点中的最近邻对，可以采用一种称为"K-d Tree"（K维树）的数据结构，尤其适用于高维空间的点查找问题。下面是基本思路：

1. **划分（Divide）**：
- 将二维平面上的点集划分为两个部分，通常选择一个坐标轴进行分割，使得每个部分包含的点集中的一维值大致相等。
- 对每个子集递归地构建K-d Tree。

2. **解决（Conquer）**：
- 查找当前节点下每个子树内的最靠近原点的点，并找到它们之间的距离作为该部分的距离上界。
- 如果这部分的距离上界小于已知的最小距离，说明可能存在更近的邻对，继续搜索；否则结束搜索。

3. **合并（Combine）**：
- 当所有子树都处理完毕后，取各个部分间的最短距离作为最终结果。这可能是全局最短距离，因为我们在每个部分都尽可能找到了局部的最优解。

**算法伪代码示例**：

function closestPair(points, kdtree) {
    // 初始化最大距离为无穷大
    let minDistance = Infinity;
    
    if (points.length <= 1) return [];
    else if (points.length == 2) return findClosestPair(points[0], points[1]);
    
    // 划分并递归处理
    const mid = Math.floor(points.length / 2);
    const leftHalf = kdtree.search(points.slice(0, mid));
    const rightHalf = kdtree.search(points.slice(mid));

    // 求两半的结果并合并
    const [leftMin, rightMin] = [
        closestPair(leftHalf, kdtree),
        closestPair(rightHalf, kdtree)
    ];
    
    // 更新最小距离和结果
    minDistance = Math.min(minDistance, leftMin.distance, rightMin.distance);

    return minDistance === leftMin.distance ? leftMin : rightMin;
}

// 假设kdtree构造函数已经实现并支持查询操作
const tree = buildKDTree(points);
const result = closestPair(tree.root, tree);