如何在线性时间内用2-近似算法找点集中的最远点对

要解决在n个点的点集中找到一对距离至少为真实最远点对距离（直径）一半的点对，且保证线性时间复杂度，完全不需要用到WSPD（其构造复杂度O(n logn)不符合要求），下面是两种高效的线性时间方法：

方法1：两次遍历法（确定性） #

• 步骤：
  1. 从点集中任选一个点p，遍历所有点找到与p距离最远的点q（O(n)时间）
  2. 再次遍历所有点，找到与q距离最远的点r（O(n)时间）
  3. 返回点对(q, r)
• 正确性证明：
  设真实直径为D = dist(a, b)。根据三角不等式，dist(a, b) ≤ dist(a, q) + dist(q, b)。而q是离p最远的点，因此dist(q, a) ≤ dist(p, q)，dist(q, b) ≤ dist(p, q)，代入得D ≤ 2*dist(p, q)，即dist(p, q) ≥ D/2。后续找到的r与q的距离只会大于等于dist(p, q)，因此必然满足dist(q, r) ≥ D/2。

方法2：随机采样验证法 #

• 步骤：
  1. 随机选取一个点s，遍历所有点找到离s最远的点t（O(n)时间）
  2. 返回点对(s, t)
• 正确性证明：
  同样基于三角不等式，真实直径D = dist(a, b)，则dist(a, b) ≤ dist(a, s) + dist(s, b) ≤ 2*max(dist(a, s), dist(s, b)) ≤ 2*dist(s, t)，因此dist(s, t) ≥ D/2。随机采样不影响时间复杂度，整体仍为O(n)。

两种方法都只需要常数次线性遍历，完全符合线性时间要求，实现简单且高效，不需要依赖任何复杂的空间划分或分解结构。

内容的提问来源于stack exchange，提问作者ricolxwz