最近点対

【さいきんてんつい (shortest point pair)】

有限個の点が空間に固定されたとき, 2点間の距離の最小値を実現する点対を最近点対という. 最近点対はドロネーグラフの辺なので, 2次元の最近点対を求めるときには, まずドロネーグラフを作って点対の候補をしぼるのが効率がよい.