xvii. Manhattan Geometry

Distance measured along axes: $d_{1} (p, q) = ∣ Δ x ∣ + ∣ Δ y ∣$ . Grid movement, city blocks, and taxicab problems.

The rotation trick — the one thing to remember

$L_{1} in (x, y) ⟷ L_{\infty} in (u, v) = (x + y, x - y) .$
$∣ Δ x ∣ + ∣ Δ y ∣ = max (∣ Δ u ∣, ∣ Δ v ∣)$

— proved in Primitives. Rotating by 45° (and scaling by $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
ll u = x + y, v = x - y;
// inverse
ll xback = (u + v) / 2, yback = (u - v) / 2;   // exact iff u, v have the same parity (true whenever x, y are integers)

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 $2 r \times 2 r$ square

Proof: the inverse transform is exact on integers

$u = x + y$ , $v = x - y$ gives $u + v = 2 x$ and $u - v = 2 y$ , so $x = (u + v) /2$ , $y = (u - v) /2$ — exact division whenever $u + v$ and $u - v$ are even, which holds automatically since $u + v = 2 x$ is even by construction for any integer $x$ (and likewise $u - v = 2 y$ ). So the round trip is lossless on the integer lattice: every $(u, v)$ arising from an integer $(x, y)$ recovers it exactly, with no rounding. $■$

Chebyshev distance

$d_{\infty} (p, q) = max (∣ Δ x ∣, ∣ Δ y ∣)$

— the number of king moves on a chessboard. The inverse rotation converts Chebyshev back to Manhattan.

Proof: king-move distance is Chebyshev

A king can change $x$ by $\pm 1$ and $y$ by $\pm 1$ in the same move, so each move reduces $max (∣ Δ x ∣, ∣ Δ y ∣)$ by at most 1 (both coordinates move toward the target simultaneously along the move that decreases the larger gap, or decreases both if equal) — giving $\geq max (∣ Δ x ∣, ∣ Δ y ∣)$ moves needed. Exactly that many suffice: move diagonally while both gaps remain positive (reducing both by 1 per move), then move straight along the one remaining nonzero axis — reaching the target in exactly $max (∣ Δ x ∣, ∣ Δ y ∣)$ moves. $■$

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 lo g n)$ by sorting:

ll sumAbsDiff(vector<ll> a) {
    sort(a.begin(), a.end());
    ll total = 0, pref = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        total += (ll)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.

Proof: sumAbsDiff

Once sorted, $\sum_{i < j} ∣ a_{i} - a_{j} ∣ = \sum_{i < j} (a_{j} - a_{i})$ (since $j > i$ in sorted order means $a_{j} \geq a_{i}$ , so the absolute value is just the difference). Fix $i$ : it contributes $+ a_{i}$ for each of the $n - 1 - i$ later elements subtracting it, and $- a_{i}$ for each of the $i$ earlier elements it subtracts — net contribution $a_{i} \cdot ((n - 1 - i) - i)$ summed differently than the code’s running form, but equivalently: processing left to right, at index $i$ every earlier element $a_{0}, \dots, a_{i - 1}$ has already been paired once with $a_{i}$ as $a_{i} - a_{j}$ (since $a_{i} \geq a_{j}$ now), contributing $i \cdot a_{i} - (a_{0} + \dots + a_{i - 1}) = i \cdot a_{i} - pref$ — exactly the code’s increment — and summing this over all $i$ accounts for every pair $(j, i)$ with $j < i$ exactly once. $■$

Tested against the brute-force $O (n^{2})$ double sum on random integer arrays.

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 lo g n)$ (or $O (n)$ with nth_element) answer, whereas the Euclidean version (the geometric median) has no closed form.

Proof: the median minimises the sum of absolute deviations

For one coordinate, $f (m) = \sum_{i} ∣ a_{i} - m ∣$ is piecewise linear and convex (a sum of convex functions). Its derivative where differentiable is $(# {a_{i} < m}) - (# {a_{i} > m})$ (each term contributes $+ 1$ or $- 1$ depending on which side of $m$ it’s on); this is negative while fewer than half the points are below $m$ , zero (or changes sign) once $m$ reaches the median, and positive beyond — so $f$ is minimised at any median (the middle element for odd $n$ , any value between the two middle elements for even $n$ ). Since the $x$ - and $y$ -sums are independent, minimising each coordinate’s median independently minimises the total $\sum d_{1} = \sum ∣ x_{i} - m_{x} ∣ + \sum ∣ y_{i} - m_{y} ∣$ . $■$

For a weighted version, take the weighted median.

The Manhattan MST

The minimum spanning tree under $L_{1}$ has a beautiful $O (n lo g 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.

Proof: only the nearest neighbour per octant can be an MST edge

Partition the plane around a point $p$ into 8 octants of $45°$ each (e.g. bounded by the axes and the two diagonals through $p$ ). Within one fixed octant, for any two points $q, r$ both in it (relative to $p$ ), one of $d_{1} (p, q) \leq d_{1} (p, r)$ or vice versa implies a triangle inequality shortcut: in the octant where, say, $0 \leq Δ y \leq Δ x$ relative to $p$ for both $q$ and $r$ , Manhattan distance equals $Δ x + Δ y$ , which coincides with a simpler monotone relationship — specifically, if $q$ is the closer of the two to $p$ in this octant, then $d_{1} (q, r) \leq d_{1} (p, r)$ (the closer point $q$ , lying “between” $p$ and the octant’s far reaches in both coordinate senses, is never farther from $r$ than $p$ is). So in any spanning tree, an edge from $p$ directly to the farther point $r$ in that octant can be replaced by $p \to q \to r$ (both edges no longer than $p \to r$ ) without increasing total weight — making the direct edge to anything but the nearest point in each octant redundant for a minimum spanning tree. Hence it suffices to consider, for every point, its nearest neighbour in each of the 8 octants: $O (n)$ candidate edges in total, sufficient to contain a minimum spanning tree (by the standard cut-property argument: a true MST edge not among these candidates could always be shortened by routing through the relevant nearest neighbour, contradicting minimality). $■$

$O (n lo g n)$ instead of $O (n^{2} lo g 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 $2$ (or 1.5 as in some game engines), the distance is the “octile” metric
$d = max (∣ Δ x ∣, ∣ Δ y ∣) + (2 - 1) min (∣ Δ x ∣, ∣ Δ y ∣),$
which is the standard admissible heuristic for grid A*.

Proof: the octile distance formula

Write $M = max (∣ Δ x ∣, ∣ Δ y ∣)$ , $m = min (∣ Δ x ∣, ∣ Δ y ∣)$ . The optimal path takes $m$ diagonal moves (covering $m$ in both axes at once, cost $m 2$ ) followed by $M - m$ straight moves along the remaining axis (cost $M - m$ ) — total $m 2 + (M - m) = M + m (2 - 1)$ , matching the formula. This is optimal because diagonal moves are strictly more “efficient” per unit of $max$ -progress whenever both axes still have remaining distance to cover (a diagonal move advances both coordinates for one unit of cost $2 \approx 1.41$ , versus two straight moves costing $2$ to achieve the same net advancement in both axes), so using as many diagonals as possible (i.e. $m$ of them, until the shorter axis is exhausted) minimises total cost. $■$

whoashish's cp notes

Directory

xvii. Manhattan Geometry

The rotation trick — the one thing to remember

Immediate consequences

Chebyshev distance

Sum of pairwise Manhattan distances

Minimising the sum of distances

The Manhattan MST

Where Manhattan geometry appears

Diagonal movement

Graph View

Table of Contents