平面最近点对

Summary

平面最近点对问题求 n 个点中距离最小的一对。采用分治：先按 x 坐标把点集二分，递归求出左右两半各自的最近距离，取较小者记为 d。跨越中线的点对只可能落在到中线水平距离小于 d 的窄带内，于是把带内点按 y 坐标排序，每个点仅需与其后有限个点依次比较即可更新答案。合并这一步为线性，加上递归与排序，整体复杂度 O(nlogn)。文末附一道模板例题，可作为分治求几何最值的入门。

参考资料

• 平面最近点对 - OI Wiki

简介

平面最近点对 问题求 $n$ 个点中距离最小的一对。分治法按 $x$ 坐标把点集二分，递归求左右两半的最近距离 $d$，再只需检查横坐标落在中线左右 $d$ 范围内、且纵坐标相近的点对，整体复杂度 $O(n\log n)$。

例题

洛谷 P1429 平面最近点对（加强版）

给定平面上 $n$ 个点，求距离最近的两个点之间的欧几里得距离。