Sign in to watch this lesson
Advanced - Geometry · 4:24
Manhattan Distance Tricks
Manhattan distance |Δx| + |Δy| is a sum of one term per coordinate, and that makes three tricks possible. Writing each absolute value as a max of signs turns the farthest pair into max - min of x + y and of x - y (2^d sign masks in d dimensions); the integer map (x, y) → (x + y, y - x) turns Manhattan distance into Chebyshev distance and diamonds into axis-aligned squares. A Manhattan minimum spanning tree only needs each point's nearest neighbour in each of 8 octants, found by a sweep over x + y with an ordered map in 4 passes, then Kruskal.
You will learn
- Compute Manhattan distances and explain why every monotone grid path between two points has the same length
- Find the farthest pair (or answer farthest-point queries) with 2^d sign masks in O(n · 2^d · d)
- Use the map (x, y) → (x + y, y - x) to turn Manhattan into Chebyshev distance with integer coordinates
- Build a Manhattan MST from at most 4n octant-neighbour candidates found by a sweep, then Kruskal