Manhattan distance, also known as L1 distance, taxicab geometry, or city block distance, is a way to calculate the distance between two points in a grid-like space. Unlike Euclidean distance, which measures the shortest straight line between two points, Manhattan distance calculates the sum of the absolute differences of their Cartesian coordinates. It represents the shortest path a taxicab would take in a city laid out in a grid.
Core Mathematical Properties of Manhattan Distance
Manhattan distance is a valid metric in mathematics, meaning it satisfies several fundamental axioms that define a distance function. These properties ensure its consistency and utility in various applications.
- Non-negativity: The distance between two points is always greater than or equal to zero.
- $d(p, q) \ge 0$
- Identity of Indiscernibles: The distance between two points is zero if and only if the points are identical.
- $d(p, q) = 0 \iff p = q$
- Symmetry (or Commutativity): The distance from point $p$ to point $q$ is the same as the distance from point $q$ to point $p$.
- $d(p, q) = d(q, p)$
- Triangle Inequality: The direct distance from point $p$ to point $r$ is always less than or equal to the sum of the distances from $p$ to an intermediate point $q$ and then from $q$ to $r$.
- $d(p, r) \le d(p, q) + d(q, r)$
Formula and Calculation
For two points $p = (x_1, y_1)$ and $q = (x_2, y_2)$ in a two-dimensional Cartesian coordinate system, the Manhattan distance is calculated as:
$D_{Manhattan}(p, q) = |x_1 - x_2| + |y_1 - y_2|$
In higher dimensions, for points $p = (p_1, p_2, ..., p_n)$ and $q = (q_1, q_2, ..., q_n)$, the formula generalizes to:
$D{Manhattan}(p, q) = \sum{i=1}^{n} |p_i - q_i|$
Example:
To find the Manhattan distance between point A (1, 2) and point B (4, 6):
$D{Manhattan}(A, B) = |1 - 4| + |2 - 6|$
$D{Manhattan}(A, B) = |-3| + |-4|$
$D_{Manhattan}(A, B) = 3 + 4 = 7$
Unique Characteristics and Geometric Insights
Beyond its fundamental metric properties, Manhattan distance possesses several distinct characteristics that set it apart, particularly in grid-based environments.
- Axis-Aligned Paths: Paths whose length equals the Manhattan distance between two points consist solely of movements along the horizontal and vertical axes. These "straight paths" in a grid sense are constrained to grid lines. This means all steps taken must be either perfectly horizontal or perfectly vertical.
- Finite Number of Optimal Paths: For any two distinct points, there are a finite number of paths between them whose length is exactly equal to the Manhattan distance. Unlike Euclidean distance, where a single straight line is the unique shortest path, Manhattan distance allows for multiple "shortest" paths that involve different sequences of horizontal and vertical moves.
- "Diamond" Shape of Equidistance: For a given point, all other points that are at a specific Manhattan distance from it form a shape that resembles a square rotated by 45 degrees, often called a diamond or lozenge. This contrasts with Euclidean distance, where points of equal distance form a perfect circle.
- L1 Norm: Manhattan distance is formally known as the L1 norm of the difference vector between two points. This places it within a broader family of Minkowski distances.
Comparison with Euclidean Distance
While both are distance metrics, Manhattan and Euclidean distances are used in different contexts due to their inherent differences.
| Feature | Manhattan Distance | Euclidean Distance |
|---|---|---|
| Path Definition | Sum of absolute differences along axes | Straight line between points |
| Formula (2D) | $ | x_1 - x_2 |
| Geometry | "City block," "taxicab" | "As the crow flies" |
| Shapes of Equidistant Points | Diamond/Square (rotated 45 degrees) | Circle |
| Sensitivity to Obstacles | Naturally models grid-like obstacles | Ignores grid, assumes clear path |
| Norm Name | L1 norm | L2 norm |
Practical Applications
Manhattan distance finds extensive use in scenarios where movement is restricted to a grid or along orthogonal axes.
- City Navigation: It accurately models walking or driving distances in cities with a grid-like street layout, where diagonal movement is often not possible.
- Computer Graphics and Image Processing: Used in algorithms for image analysis, feature extraction, and pathfinding on pixel grids, where movement is typically pixel-by-pixel, horizontally or vertically.
- VLSI Design: Crucial for calculating wire lengths in integrated circuits, as wires are laid out along orthogonal paths on a chip.
- Chess: The movement of a Rook on a chessboard is a direct application of Manhattan distance, as it can only move horizontally or vertically.
- Data Science and Machine Learning: Employed in certain clustering algorithms (e.g., K-means for specific data types), classification, and similarity measures, especially when dealing with high-dimensional data or features that represent independent orthogonal components.
- Robotics: For robot navigation in structured environments where movement is restricted to cardinal directions.
Why Choose Manhattan Distance?
Choosing Manhattan distance often comes down to the nature of the space and the type of movement being modeled. It is preferred when diagonal movement is not permitted or is less efficient than axial movement, or when the "cost" of moving along each dimension is considered independently and additively. Its simplicity and computational efficiency also make it valuable in various algorithms.
