如下： 1985年 Preparata 和 Shamos 在给出该问题的一个分治算法并且还具体分析了在 [mid−dis,mid+dis][mid-dis,mid+dis][mid−dis,mid+dis] 区域中出现的情况，若 (p,q)(p,q)(p,q) 是 QQQ 的最近点对，ppp 在带域左半部分，则 qqq 点必在下图所示的 δ∗2δ\delta* 2\deltaδ∗2δ 长方形上，而在该长方形上，最多只能由右边点集的6个点。每个点对之间的距离不小于δ。

  此结论很好证明，通过在 δ∗2δ\delta* 2\deltaδ∗2δ 上以 2δ3∗δ2\frac{2\delta}{3}* \frac{\delta}{2}32δ​∗2δ​ 划成 666 个小长方形

  用反证法来证明，假设存在大于6个点，则必有一个或多个小长方形存在两个及以上点，而小长方形的最长距离是为对角线长度，为： (2δ3∗2δ3+δ2∗δ2)=56δ<δ\sqrt{(\frac{2\delta}{3}\frac{2\delta}{3}+\frac{\delta}{2}\frac{\delta}{2})}=\frac{5}{6}\delta<\delta(32δ​∗32δ​+2δ​∗2δ​) ​=65​δ<δ。最长距离都小于δ，与之前的条件不符合，故最多有6个点。借此，可以将可能的线性时间缩小到常数级，大大提高了平均时间复杂度。 这个描述我并没有理解到对本题的优化有什么用处，大佬们求教！