座標での最近点 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

座標での最近点を高速で求める方法を書く。
点の数はN個とする。

マンハッタン距離

とりあえず2次元だとする。多次元にも拡張できると思う。
ナイーブな実装では全点間のペアを試さないといけない。これでは、点ごとに候補がN-1個存在することになる。計算量はO(N^2)

ここで、うまく候補を絞ってみる。
今見てる頂点を(a, b)とする。
{マンハッタン距離が一番近いものは、必ず、
x座標に関しては、点の列の中でのソートされたものの中でx = aの一つ手前と一つ奥である。
同様にy座標に関しては、y = bの一つ手前と奥である。}(ソートされた列内での一つ手前や奥。ソートするとき、x軸でするものなら、第一比較にx第二比較にy、y軸でするものなら、第一比較にy第二比較にxである)
証明すると、そのうちの4つの点に入らないということは、4点に対するマンハッタン距離が同じとなる斜め45度の4つの正方形の内部に今考えてる頂点がないということである。内部にあるのならば、必ずx = aもしくはy = bにより近くなるためである。よって、その4点の候補内にマンハッタン距離最近点がある。

ARC076 D(500)

https://atcoder.jp/contests/arc076/tasks/arc076_b

この問題は上記の考え方のとおりではないが、似ている。
ある3点を考えるとき、それらをつなげるときに一番コストがかからないのは、軸ごとに独立で考えると、一つ手前か後が候補として残る。それらの候補の中で、コストの低い順にクラスカルすれば解ける。