マッチング (平面上の)

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

与えられた平面上の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n=2m\,} 個の点集合に対して, 2点ずつペアにして$m\,$個のペアの集合(完全マッチング)$M\,$を作る問題で, 特に, ペアの重みをそのペアに含まれる2点間の距離(2点を結ぶ線分の長さ)とし, 完全マッチング構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\,} の重みを$M\,$に含まれる$m\,$個のペアの重みの総和として, 重みを最小にする完全マッチング構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M^*\,} を見つける問題を平面最小重み完全マッチングという. この問題は${\mbox{O}}(n^{3})\,$の手間で解けるが, バケット法に基づけば近似的に${\mbox{O}}(n)\,$の手間で解ける.