Manhattan Minimum Spanning Tree
問題
解法
- NOTE: ここで述べる解法は基本的に以下の topcoder の記事を参考に分割統治部分を座標圧縮+セグメント木で置き換えたものである.
ナイーブに考えると,全点対でマンハッタン距離を計算して Kruskal 法などの最小全域木を求めるアルゴリズムを適用すればよいと思えるが,この解法では入力の頂点数 \(N\) に対して,枝数が \(O(N^2)\) になってしまう.
実は全点対を考える必要はなくて,マンハッタン距離で最小になる点の間で枝を貼るだけでよい(要証明).この方法によって枝数が \(O(N)\) になり,解法の計算量を \(O(N \log N)\) にすることができる.
ではここからは,ある点 P に対してマンハッタン距離が最短になる点を求める方法を説明する.ある点 P とマンハッタン距離が最短になる点を以下の図のような 8 方向の領域のそれぞれで探索し,その 8 …
more ...