Manhattan Distance

For points p and q in the plane,

d(p, q) = |xₚ − x_q| + |yₚ − y_q|

This is Manhattan (taxicab) distance: you may only move horizontally or vertically, like on a city grid. Many shortest paths can share the same length.

This lesson follows CP-Algorithms — Manhattan distance.

Related: Basic Geometry.

Farthest pair (Manhattan)

Given n points, maximize |xₚ−x_q| + |yₚ−y_q|.

1D warm-up (y = 0):

|xₚ − x_q| = max(xₚ − x_q, −xₚ + x_q)

So the maximum is max x − min x (one sign pattern wins; the other is smaller).

d dimensions: try all 2ᵈ sign masks. For a fixed mask, each point gets a scalar

cur = ±x₀ ± x₁ ± … ± x_{d−1}

and the mask’s contribution is max(cur) − min(cur). Take the best over masks.

Time: O(n · 2ᵈ · d).

long long ans = 0;
for (int msk = 0; msk < (1 << d); msk++) {
    long long mx = LLONG_MIN, mn = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        long long cur = 0;
        for (int j = 0; j < d; j++) {
            if (msk & (1 << j)) cur += p[i][j];
            else cur -= p[i][j];
        }
        mx = max(mx, cur);
        mn = min(mn, cur);
    }
    ans = max(ans, mx - mn);
}

In 2D the four masks are essentially extrema of ±x ± y (e.g. x+y, x−y, …).

🧪 Farthest Manhattan pair (2D)

Rotate to Chebyshev

Identity (check signs of m, n):

|m| + |n| = max(|m + n|, |m − n|)

Applied to Manhattan:

|x₁−x₂| + |y₁−y₂|
  = max( |(x₁+y₁)−(x₂+y₂)| , |(y₁−x₁)−(y₂−x₂)| )

That is the Chebyshev (L∞) distance of

α(x, y) = (x + y, y − x)

So after α, Manhattan problems become Chebyshev problems (axis-aligned squares instead of diamonds). Geometrically α is a 45° rotation about the origin plus scale √2.

Manhattan MST — `O(n log n)`

Connect all points with minimum total Manhattan edge weight (assume distinct locations).

Key fact: it is enough to keep, for each point, its nearest neighbor in each octant (8 cones). For s and any two points p, q in the same octant,

d(p, q) < max(d(s, p), d(s, q))

so an MST never needs both s–p and s–q. That yields O(n) candidate edges; then run Kruskal.

Nearest neighbor per octant

Focus on the NNE octant; other directions follow by rotating the cloud (4 rotations suffice in the KACTL-style code — each also covers the opposite octant).

Sweep by non-decreasing x + y. Keep an active set of points still waiting for a neighbor in this octant, ordered by x.

When processing p:

Walk active points with x ≤ xₚ from large x downward while xₚ − yₚ ≤ xₛ − yₛ (NNE condition).
Each such s gets nearest neighbor p (distance (xₚ+yₚ)−(xₛ+yₛ)); erase them.
Insert p into active.

Amortized O(n log n) per rotation. Then Kruskal on the candidate list.

struct point { long long x, y; };

// Edges (weight, u, v) — feed to Kruskal for the Manhattan MST.
vector<tuple<long long, int, int>> manhattan_mst_edges(vector<point> ps) {
    vector<int> ids(ps.size());
    iota(ids.begin(), ids.end(), 0);
    vector<tuple<long long, int, int>> edges;
    for (int rot = 0; rot < 4; rot++) {
        sort(ids.begin(), ids.end(), [&](int i, int j) {
            return (ps[i].x + ps[i].y) < (ps[j].x + ps[j].y);
        });
        map<int, int, greater<int>> active; // x -> id
        for (auto i : ids) {
            for (auto it = active.lower_bound(ps[i].x); it != active.end();
                 active.erase(it++)) {
                int j = it->second;
                if (ps[i].x - ps[i].y > ps[j].x - ps[j].y) break;
                edges.push_back({
                    (ps[i].x - ps[j].x) + (ps[i].y - ps[j].y), i, j});
            }
            active[ps[i].x] = i;
        }
        for (auto &p : ps) { // rotate 90° steps (swap / flip)
            if (rot & 1) p.x *= -1;
            else swap(p.x, p.y);
        }
    }
    return edges;
}

🧪 Candidate edges + Kruskal weight

Check: Manhattan tricks

Quiz