マッチング (平面上の)のソースを表示

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

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