Manhattan Geometry

Distance measured along axes: $d_1(p,q)=|\Delta x|+|\Delta y|$. Grid movement, city blocks, and taxicab problems.

The rotation trick — the one thing to remember

$L_1\text{ in }(x,y)⟷L_{\infty }\text{ in }(u,v)=(x+y,x-y).$

$|\Delta x|+|\Delta y|=\max (|\Delta u|,|\Delta v|).$

Rotating by 45° (and scaling by $\sqrt{2}$) turns Manhattan into Chebyshev, which decouples the coordinates — and $\max$ over independent coordinates is far easier to optimise than a sum of absolute values.

// transform
u = x + y;  v = x - y;
// inverse
x = (u + v) / 2;  y = (u - v) / 2;

Immediate consequences

Problem	With the rotation
Maximum Manhattan distance among $n$ points	$\max (\max u-\min u,\max v-\min v)$ — $O(n)$
Maximum $L_1$ distance in $d$ dimensions	$\max$ over $2^{d-1}$ sign patterns of $\sum \pm x_i$ — $O(2^{d}n)$
Manhattan balls (diamonds)	become axis-aligned squares
Do two diamonds intersect?	do two squares intersect — trivial
Manhattan nearest neighbour	Chebyshev nearest neighbour
Points within Manhattan distance $r$	points in a $2r\times 2r$ square

Chebyshev distance

$d_{\infty }(p,q)=\max (|\Delta x|,|\Delta y|)$

— the number of king moves on a chessboard. The inverse rotation $(x,y)\to \left(\frac{x+y}{2},\frac{x-y}{2}\right)$ converts Chebyshev back to Manhattan.

Sum of pairwise Manhattan distances

Because the coordinates are independent,

${\sum }_{i<j}{d}_1(p_i,p_j)={\sum }_{i<j}|x_i-x_j|+{\sum }_{i<j}|y_i-y_j|,$

and each term is computed in $O(n\log n)$ by sorting:

long long sumAbsDiff(vector<long long> a) {
    sort(a.begin(), a.end());
    long long total = 0, pref = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        total += (long long)i * a[i] - pref;
        pref += a[i];
    }
    return total;
}

This separability is the defining advantage of $L_1$ over $L_2$, and it makes many “sum of distances” problems easy that would be intractable in Euclidean geometry.

Minimising the sum of distances

The point minimising $\sum d_1(p,q_i)$ is the coordinate-wise median — independently in $x$ and in $y$. That is an $O(n\log n)$ (or $O(n)$ with nth_element) answer, whereas the Euclidean version (the geometric median) has no closed form.

For a weighted version, take the weighted median.

The Manhattan MST

The minimum spanning tree under $L_1$ has a beautiful $O(n\log n)$ algorithm:

For each point, only its nearest neighbour in each of 8 octants can be an MST edge.

So sweep in 4 directions (each covering 2 octants by symmetry), using a BIT to find the nearest candidate, producing $O(n)$ candidate edges; then run Kruskal.

$O(n\log n)$ instead of $O(n^2\log n)$ on the complete graph. The Euclidean analogue needs Delaunay; the Manhattan one needs only sorting and a BIT, which makes it considerably more approachable.

Where Manhattan geometry appears

Problem	Note
Grid movement (4 directions)	distance = $L_1$
King moves	distance = $L_{\infty }$
VLSI routing	wires run along axes
Warehouse / facility placement	median minimises total travel
Taxicab problems	the name
”Rotate the grid 45°” puzzles	the transformation above
Rectilinear Steiner tree	NP-hard, unlike the MST
Rectangle union / stabbing	axis-aligned throughout

Diagonal movement

On a grid where diagonal moves also cost 1, the distance is Chebyshev. If diagonals cost $\sqrt{2}$ (or 1.5 as in some game engines), the distance is the “octile” metric

$d=\max (|\Delta x|,|\Delta y|)+(\sqrt{2}-1)\min (|\Delta x|,|\Delta y|),$

which is the standard admissible heuristic for grid A*.

See also: Distances · Sweep Line · Minimum Spanning Tree