最近点对

问题描述

给定平面上 $m$ 个点的集合 $S$,找其中的一对点使得在 $n$ 个点组成的所有点对中,该点对间的距离最小。

问题分析

简单情形:一维数轴

为了使问题易于理解和分析,先来考虑一维的情形。此时 $S$ 中的 $n$ 个点退化为 $x$ 轴上的 $n$ 个实数 $x_1, x_2, \cdots, x_n$。最接近点对即为这 $n$ 个实数中相差最小的 $2$ 个实数。

假设用 $x$ 轴上某个点 $m$ 将 $S$ 划分为小于 $m$ 的子集 $S_1$ 和大于 $m$ 的子集 $S_2$。基于平衡子问题的思想,用 $S$ 中各点坐标的中位数来作分割点。在 $S_1$ 中找出其最近点对 ${p_1, p_2} (p_1 > p_2)$,在 $S_2$ 中找出其最近点对 ${q_1, q_2} (q_1 < q_2)$。于是最短距离分别为

$$ \begin{align} d_{S_1} &= \left | p_1 - p_2 \right | \\\\ d_{S_2} &= \left | q_1 - q_2 \right | \end{align} $$

递归地,$S$ 中的最近点对要么是 $\{p_1, p_2\}$,要么是 $\{q_1, q_2\}$,要么是某个点对 $\{p_3, q_3\}$,其中 $p_3 \in S_1$ 且 $q_3 \in S_2$。从而用线性时间就可以将 $S_1$ 的解和 $S_2$ 的解合并成为 $S$ 的解。

$$ \begin{align} d = \min (d_{S_1}, d_{S_2}, q_3 - p_3) \end{align} $$

复杂情形:二维平面

选取一垂直线 $l:x=m$ 来作为分割直线。其中 $m$ 为 $S$ 中各点 $x$ 坐标的中位数。由此将 $S$ 分割为 $S_1$ 和 $S_2$ 两个半平面。

递归地在 $S_1$ 和 $S_2$ 上找出其最小距离 $d_1$ 和 $d_2$ 并设 $d=\min(d_1, d_2)$。$S$ 中的最接近点对要么是 $d$,要么是某个 ${p, q}$,其中 $p \in S_1$ 且 $q \in S_2$。如图所示:

对于点 $p \in P_1$,需要考察 $P_2$ 中的各个点和点 $p$ 之间的距离是否小于 $d$。显然 $P_2$ 中这样点的 $y$ 轴坐标一定位于区间 $[y-d, y+d]$ 之间,而且,这样的点不会超过 $6$ 个。

快速检查 $6$ 个点的方法

  • 将 $P_1$ 和 $P_2$ 中所有 $S$ 中点按其 $y$ 坐标排好序(预处理)。
  • 对 $P_1$ 中所有点,对排好序的点列作一次扫描。
  • 对 $P_1$ 中每一点最多只要检查 $P_2$ 中排好序的相继 $6$ 个点。

算法分析

一维简单情形和二维情形的时间复杂度均为

$$ \begin{align} T(n) &= 2 T\left( \frac{n}{2} \right) + O(n) \\\\ &= O(n \log {n}) \end{align} $$
Previous
Next