如何求解满足L<R及坐标区间限制的二维点集最近对距离？

结论 #

该点集的全局最近对距离为L

推导过程 #

全局最近对只可能属于以下三类点对，我们逐一分析最小值：

• 两点均位于x负半区：该类的最小距离为已知条件L
• 两点均位于x正半区：该类的最小距离为已知条件R，且题目明确给出L < R，因此该类最小值大于L
• 跨半区点对（一个点x坐标为负，一个点x坐标为正）：
  根据题目约束，没有点的x坐标落在区间(-L/2, R/2)内，因此所有x负的点的x坐标满足x ≤ -L/2，所有x正的点的x坐标满足x ≥ R/2。
  跨区点对的x坐标差满足：
  Δx ≥ R/2 - (-L/2) = (L + R)/2
  结合L < R可得：
  Δx > (L + L)/2 = L
  而欧氏距离的计算公式为√(Δx² + Δy²) ≥ Δx，因此所有跨区点对的距离都大于L。

综上三类点对的最小值均不小于L，且存在负半区的点对距离等于L，因此全局最近对距离为L。

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