Manhattan & Chebyshev Distances

L1 (Manhattan) is a diamond, L∞ (Chebyshev) is a square. The 45° rotation u = x+y, v = x−y turns the diamond into the square — and turns O(n²) max-Manhattan-distance into an O(n) scan.

L1 · |dx|+|dy| · diamond L2 · √(dx²+dy²) · circle L∞ · max(|dx|,|dy|) · square
slow fast
L1 diamond
L2 circle
L∞ square
winning pair

What's happening

Pick a tab. Unit Balls shows the three metric shapes; 45° Rotation morphs the diamond into a square; Max Manhattan solves the farthest-pair problem via the rotation.

Complexity

OperationTime
L1 / L∞ distanceO(1)
Rotate a pointO(1)
Max Manhattan (naive)O(n²)
Max Manhattan (rotation)O(n)
Min Σ L1 (median)O(n log n)
Manhattan MSTO(n log n)

Operation Log