Manhattan Distance

TL;DR

• Measures distance on a grid by summing absolute coordinate differences across dimensions.
• Reflects the number of horizontal and vertical steps between points in grid-based spaces.
• Commonly used as a cost estimate (heuristic) in pathfinding and as a similarity measure in clustering.

Definition

The Manhattan distance, also known as the taxicab distance, is a measure of distance between two points in a grid-based system. It is calculated by taking the absolute difference of the two points’ coordinates in each dimension and summing those differences.

Formally, for two points x and y in n dimensions:

$$d_{\text{Manhattan}}(x,y)=\sum_{i=1}^n |x_i - y_i|$$

Explanation

To compute the Manhattan distance, compute the absolute difference for each corresponding coordinate of the two points, then sum those absolute differences. The result represents the total number of axis-aligned steps (e.g., horizontal and vertical) required to move from one point to the other on a grid.

Examples

2-dimensional example (points A and B)

Point A: (3,5)
Point B: (6,2)

Compute per-dimension absolute differences: $|3-6| = 3$ $|5-2| = 3$

Sum: $3 + 3 = 6$

Manhattan distance between A and B = 6.

3-dimensional example (points C and D)

Point C: (7,4,2)
Point D: (1,3,9)

Compute per-dimension absolute differences: $|7-1| = 6$ $|4-3| = 1$ $|2-9| = 7$

Sum: $6 + 1 + 7 = 14$

Manhattan distance between C and D = 14.

Use cases

• Pathfinding algorithms in computer science: used to determine the “cost” of moving between grid cells, representing required horizontal and vertical steps.
• Clustering algorithms in machine learning: used to measure similarity between points; smaller distances indicate closer relationships.

Notes or pitfalls

• The Manhattan distance satisfies the triangle inequality, so it is a valid metric for algorithms that require this property.
• It is often used as a heuristic in pathfinding algorithms to provide an estimate of the cost to reach a goal, enabling efficient approximate solutions.

Related terms

• Taxicab distance
• Heuristic
• Triangle inequality
• Pathfinding
• Clustering