マッチング (平面上の)

【まっちんぐ (matching in the plane)】

与えられた平面上の$n=2m\,$個の点集合に対して, 2点ずつペアにして$m\,$個のペアの集合(完全マッチング)$M\,$を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング$M\,$の重みを$M\,$に含まれる$m\,$個のペアの重みの総和として, 重みを最小にする完全マッチング$M^{*}\,$を見つける問題を平面最小重み完全マッチングという. この問題は${\mbox{O}}(n^{3})\,$の手間で解けるが, バケット法に基づけば近似的に${\mbox{O}}(n)\,$の手間で解ける.