本节介绍使用分治法查找最接近的点对的有效算法。给定一组点，最近对问题是找到彼此最接近的两个点。如下图所示，绘制一条线来连接最近对动画中两个最近的点。

案例研究：查找最近的对，提出了一种用于查找最近的点对的强力算法。该算法计算所有点对之间的距离并找到距离最小的点。显然，该算法需要 O(n^2) 时间。我们能否设计出更高效的算法？

我们将使用一种称为分而治之的方法来解决这个问题。该方法将问题划分为子问题，求解子问题，然后组合子问题的解以获得整个问题的解。与动态规划方法不同，分而治之方法中的子问题不重叠。子问题就像原问题一样，但规模较小，因此可以应用递归来解决问题。事实上，所有递归问题的解决方案都遵循分而治之的方法。

以下步骤描述了如何使用分而治之的方法解决最近配对问题。

• 第 1 步：按 x 坐标升序对点进行排序。对于具有相同 x 坐标的点，按 y 坐标排序。这会产生一个排序的点列表 S。
• 步骤2：使用排序列表中的中点将S分为两个大小相等的子集S1和S2。令中点位于 S1 处。递归地找到 S1 和 S2 中最接近的对。令 d1 和 d2 分别表示两个子集中最近对的距离。
• 步骤3：找到S1中的点和S2中的点之间最接近的对，并将它们的距离表示为d3。最接近的一对是距离为 min(d1, d2, d3).

选择排序需要 O(n^2) 时间。步骤 1 可以在 O(n log n) 时间内完成。步骤 3 可以在 O(n) 时间内完成。设 d = min(d1, d2)。我们已经知道最近的对距离不能大于 d。为了使S1中的点和S2中的点形成S中最接近的对，左边的点必须在stripL中，右边的点在stripR中，如下图所示（ A）。

对于stripL中的点p，只需考虑d X 2d矩形内的右点，如下(b)所示。矩形外的任何右点都不能与 p 形成最接近的对。由于S2中最近对的距离大于或等于d，因此最多可以有六个
矩形内的点。因此，对于stripL中的每个点，最多需要考虑stripR中的六个点。

对于stripL中的每个点p，如何定位stripR中对应的d X 2d矩形区域中的点？如果 stripL 和 stripR 中的点按其 y 坐标的升序排序，则可以有效地完成此操作。令 pointsOrderedOnY 为按 y 坐标升序排序的点列表。 pointsOrderedOnY可以在算法中预先获得。 stripL 和 stripR 可以从步骤 3 中的 pointsOrderedOnY 获得，如下面的代码所示。

对于pointsOrderedOnY 中的每个点p
if (p 在 S1 中并且 mid.x – p.x 将 p 附加到 stripL;
else if (p 在 S2 中且 p.x - mid.x 将 p 附加到 stripR;

设stripL和stripR中的点为{p0, p1, ... , pk}和{q0, q1, ... , qt}，如图上图(c)。 stripL 中的点与 stripR 中的点之间最接近的对可以使用下面代码中描述的算法找到。

d = min(d1, d2);
 r = 0; // r is the index of a point in stripR
 for (each point p in stripL) {
 // Skip the points in stripR below p.y - d
  while (r 



stripL中的点按 p0, p1, ... , pk 的顺序考虑。对于 stripL 中的点 p，跳过 stripR 中 p.y – d 下方的点（第 5-6 行）。一旦跳过某个点，就不再考虑该点。 while 循环（第 9-17 行）检查 (p, q[r1]) 是否是可能最接近的对。这样的 q[r1] 对最多有 6 个，因为 stripR 中两点之间的距离不能小于 d。因此，在步骤 3 中找到最接近的对的复杂度是 O(n).

请注意，上述步骤中的步骤 1 仅执行一次以对点进行预排序。假设所有点都已预先排序。令 T(n) 表示该算法的时间复杂度。因此，



因此，可以在 O(n log n) 时间内找到最接近的点对。