マンハッタン距離

$u = x + y$, $v = x - y$ と変換する（45 度回転して $\sqrt{2}$ 倍する）と、 $\lvert a \rvert + \lvert b \rvert = \max(\lvert a + b \rvert, \lvert a - b \rvert)$ から $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = \max(\lvert u_1 - u_2 \rvert, \lvert v_1 - v_2 \rvert)$ が成り立ちます。マンハッタン距離が $u$ の差と $v$ の差の大きい方になるので、 $u$ と $v$ を別々に扱えます。たとえば最も遠い 2 点の距離は、 $u$ の最大値と最小値の差と、 $v$ の最大値と最小値の差のうち大きい方です。

最小全域木は、各点 $i$ から見て 45 度ずつに区切った 8 つの範囲それぞれで、 $i$ に最も近い点と $i$ を結んだ辺だけから作れます。同じ範囲にある 2 点 $j$, $k$ の距離は、 $i$ から $j$ への距離と $i$ から $k$ への距離の大きい方以下になるからです。辺に向きはないので 4 つの範囲を見れば足ります。座標を入れ替えたり符号を反転したりして同じ形の範囲にし、 $x$ 座標の大きい順に見ながら Fenwick Tree で最も近い点を探します。

manhattan_mst が返した辺だけで最小全域木を求めると、すべての 2 点の間に辺がある完全グラフの最小全域木になります。 $O(N^2)$ の Prim 法より速いです。

例（最小全域木（Kruskal・Prim） の kruskal を使う）:

ps = [(0, 0), (3, 1), (1, 4), (5, 5)]
print(manhattan_farthest(ps))  # (10, 3, 0)
es = manhattan_mst(ps)
cost, used = kruskal(len(ps), [(i, j, w) for w, i, j in es])
print(cost)  # 14
tree = [es[k] for k in used]  # 最小全域木の辺 (w, i, j)

コード

def manhattan_farthest(ps):
    # マンハッタン距離が最大の 2 点の (距離, i, j)（i, j は点の番号。点は 1 個以上）
    # |x1 - x2| + |y1 - y2| = max(|u1 - u2|, |v1 - v2|)（u = x + y, v = x - y）
    n = len(ps)
    best = (-1, 0, 0)
    for s in (1, -1):
        a = [x + s * y for x, y in ps]
        i = max(range(n), key=a.__getitem__)
        j = min(range(n), key=a.__getitem__)
        if a[i] - a[j] > best[0]:
            best = (a[i] - a[j], i, j)
    return best


def manhattan_mst(ps):
    # マンハッタン距離の最小全域木に使われうる辺 (w, i, j) のリスト（4N 本以下）
    n = len(ps)
    xs = [x for x, y in ps]
    ys = [y for x, y in ps]
    INF = float("inf")
    res = []
    for k in range(4):
        # X[j] >= X[i] かつ Y[j] - X[j] >= Y[i] - X[i] となる j（i から見て 45 度から 90 度の範囲）のうち、
        # X[j] + Y[j] が最小のものと i を結ぶ。X の大きい順に見て、Y - X の順の BIT で最小値を求める
        keys = sorted(set(y - x for x, y in zip(xs, ys)), reverse=True)
        rank = {v: r + 1 for r, v in enumerate(keys)}  # Y - X が大きいほど小さい番号
        m = len(keys)
        bv = [INF] * (m + 1)
        bi = [-1] * (m + 1)
        for i in sorted(range(n), key=lambda i: (xs[i], ys[i]), reverse=True):
            r = rank[ys[i] - xs[i]]
            s = xs[i] + ys[i]
            best, j = INF, -1
            t = r
            while t:
                if bv[t] < best:
                    best, j = bv[t], bi[t]
                t -= t & -t
            if j != -1:
                res.append((best - s, i, j))
            t = r
            while t <= m:
                if s < bv[t]:
                    bv[t], bi[t] = s, i
                t += t & -t
        # (x, y) -> (y, x) -> (-y, x) -> (x, -y) と変換して 4 つの範囲を見る
        if k % 2 == 0:
            xs, ys = ys, xs
        else:
            xs = [-x for x in xs]
    return res