マッチング (平面上の)

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

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