マッチング (平面上の)

出典: ORWiki

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

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

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0_%28%E5%B9%B3%E9%9D%A2%E4%B8%8A%E3%81%AE%29" より作成