Types of distances
A metric measures how far apart two points are, and the same two points can be at different distances under different metrics. The Euclidean distance is the straight-line distance, the taxicab distance travels along the axes, and the Chebyshev distance takes the largest difference in one coordinate. The geodesic distance is the length of the shortest path that stays on a surface, such as the great-circle distance on the Earth. The discrete metric only says whether two points are equal.
Definitions
Consider two points $p = (p_1, \dots, p_n)$ and $q = (q_1, \dots, q_n)$ in $\reals^n$. The Euclidean distance between $p$ and $q$ is the length of the straight segment from $p$ to $q$:
\[d_2(p, q) = \sqrt{(p_1 - q_1)^2 + \dots + (p_n - q_n)^2}.\]Consider two points $p = (p_1, \dots, p_n)$ and $q = (q_1, \dots, q_n)$ in $\reals^n$. The Euclidean distance between $p$ and $q$ is
\[d_2(p, q) = \norm{p - q}_2\]where $\norm{\cdot}$ indicates the Euclidean norm.
Examples
-
The north pole $p = (0, 0, 1)$ and the point $q = (1, 0, 0)$ on the equator of the unit sphere in $\reals^3$
: $d_2(p, q) = \sqrt{1^2 + 0^2 + 1^2} = \sqrt{2} \approx 1.41$
The Euclidean distance $\sqrt{2} \approx 1.41$ is shorter, because the straight segment cuts through the inside of the sphere.
-
The points $p = (0, 0)$ and $q = (100, 100)$ in $\reals^2$
: $d_2(p, q) = \sqrt{100^2 + 100^2} = 100 \sqrt{2} \approx 141.42$
In the discrete metric, they are at distance $1$, the same as every two different points, so the discrete metric does not measure size at all.
-
The points $p = (0, 0)$ and $q = (2, 0)$ in $\reals^2$
: $d_2(p, q) = \sqrt{2^2 + 0^2} = 2$
Only the discrete metric differs.
-
The points $p = (1, 1)$ and $q = (4, 5)$ in $\reals^2$
: $d_2(p, q) = \sqrt{3^2 + 4^2} = 5$
The straight-line distance is $5$, the distance along the axes is $3 + 4 = 7$, and the larger difference is $4$. Every pair of different points is at discrete distance $1$.
Consider two points $p = (p_1, \dots, p_n)$ and $q = (q_1, \dots, q_n)$ in $\reals^n$. The taxicab distance between $p$ and $q$ is the distance traveled from $p$ to $q$ when moving parallel to one axis at a time, as along the streets of a grid:
\[d_1(p, q) = \abs{p_1 - q_1} + \dots + \abs{p_n - q_n}.\]Consider two points $p = (p_1, \dots, p_n)$ and $q = (q_1, \dots, q_n)$ in $\reals^n$. The taxicab distance between $p$ and $q$ is defined as
\[d_1(p, q) = \sum_{i=1}^n \abs{p_i - q_i}.\]Examples
- The north pole $p = (0, 0, 1)$ and the point $q = (1, 0, 0)$ on the equator of the unit sphere in $\reals^3$ : $d_1(p, q) = 1 + 0 + 1 = 2$
-
The points $p = (0, 0)$ and $q = (100, 100)$ in $\reals^2$
: $d_1(p, q) = 100 + 100 = 200$
In the discrete metric, they are at distance $1$, the same as every two different points, so the discrete metric does not measure size at all.
-
The points $p = (0, 0)$ and $q = (2, 0)$ in $\reals^2$
: $d_1(p, q) = 2 + 0 = 2$
Only the discrete metric differs.
-
The points $p = (1, 1)$ and $q = (4, 5)$ in $\reals^2$
: $d_1(p, q) = 3 + 4 = 7$
The points $(1, 1)$ and $(4, 5)$ differ by $3$ in the first coordinate and $4$ in the second.
Properties
- The taxicab distance is $\norm{p - q}_1$, the 1-norm of the difference.
Consider two points $p = (p_1, \dots, p_n)$ and $q = (q_1, \dots, q_n)$ in $\reals^n$. The Chebyshev distance between $p$ and $q$ is the largest difference in any one coordinate:
\[d_{\infty}(p, q) = \max_i \abs{p_i - q_i}.\]Examples
- The north pole $p = (0, 0, 1)$ and the point $q = (1, 0, 0)$ on the equator of the unit sphere in $\reals^3$ : $d_{\infty}(p, q) = \max(1, 0, 1) = 1$
-
The points $p = (0, 0)$ and $q = (100, 100)$ in $\reals^2$
: $d_{\infty}(p, q) = \max(100, 100) = 100$
The points $(0, 0)$ and $(100, 100)$ are far apart in the Euclidean, taxicab, and Chebyshev distances, which differ by factors of up to $2$.
-
The points $p = (0, 0)$ and $q = (2, 0)$ in $\reals^2$
: $d_{\infty}(p, q) = \max(2, 0) = 2$
The points $(0, 0)$ and $(2, 0)$ lie on a line parallel to an axis, so the Euclidean, taxicab, and Chebyshev distances all equal $2$.
-
The points $p = (1, 1)$ and $q = (4, 5)$ in $\reals^2$
: $d_{\infty}(p, q) = \max(3, 4) = 4$
The points $(1, 1)$ and $(4, 5)$ differ by $3$ in the first coordinate and $4$ in the second.
Properties
- The Chebyshev distance is $\norm{p - q}_{\infty}$, the infinity norm of the difference.
- On a chessboard, the Chebyshev distance between two squares is the number of moves a king needs to go from one to the other.
Consider a set $X$. The discrete metric on $X$ is the metric $d$ such that $d(p, q) = 1$ for $p \neq q$ and $d(p, p) = 0$.
Examples
-
The north pole $p = (0, 0, 1)$ and the point $q = (1, 0, 0)$ on the equator of the unit sphere in $\reals^3$
: $d(p, q) = 1$
The discrete distance between $p = (0, 0, 1)$ and $q = (1, 0, 0)$ is $1$, because $p \neq q$.
-
The points $p = (0, 0)$ and $q = (100, 100)$ in $\reals^2$
: $d(p, q) = 1$
The discrete distance between $p = (0, 0)$ and $q = (100, 100)$ is $1$, because $p \neq q$.
-
The points $p = (0, 0)$ and $q = (2, 0)$ in $\reals^2$
: $d(p, q) = 1$
The discrete distance between $p = (0, 0)$ and $q = (2, 0)$ is $1$, because $p \neq q$.
-
The points $p = (1, 1)$ and $q = (4, 5)$ in $\reals^2$
: $d(p, q) = 1$
The discrete distance between $p = (1, 1)$ and $q = (4, 5)$ is $1$, because $p \neq q$.
- $d(x, y) = 1$ for $x \neq y$, and $d(x, x) = 0$
Properties
- The discrete metric does not come from a norm, even on $\reals^n$, because $d(2p, 0) = 1 = d(p, 0)$ for every $p \neq 0$, so it does not scale.
- In the discrete metric, every set is open, and a sequence converges only if it is eventually constant.
Consider two points $p$ and $q$ on a surface, such as two cities on the Earth. The geodesic distance between $p$ and $q$ is the length of the shortest path from $p$ to $q$ that stays on the surface.
Consider a connected Riemannian manifold $M$ and two points $p, q \in M$. The geodesic distance between $p$ and $q$ is the infimum of the lengths of the piecewise smooth curves in $M$ from $p$ to $q$:
\[d(p, q) = \inf \setdef{\int_0^1 \norm{\gamma^{\prime}(t)} \mathrm{d}t \suchthat \gamma(0) = p, \gamma(1) = q}.\]Examples
-
The north pole $p = (0, 0, 1)$ and the point $q = (1, 0, 0)$ on the equator of the unit sphere in $\reals^3$
: $\frac{\pi}{2} \approx 1.57$
The geodesic distance on the unit sphere from the north pole to a point on the equator is the length of a quarter of a great circle, $\frac{2 \pi}{4} = \frac{\pi}{2}$.
-
The points $p = (0, 0)$ and $q = (100, 100)$ in $\reals^2$
: $100 \sqrt{2}$
In the plane, the geodesic distance between $p$ and $q$ equals the Euclidean distance, because the straight segment from $p$ to $q$ stays in the plane.
-
The points $p = (0, 0)$ and $q = (2, 0)$ in $\reals^2$
: $2$
In the plane, the geodesic distance between $p$ and $q$ equals the Euclidean distance, because the straight segment from $p$ to $q$ stays in the plane.
-
The points $p = (1, 1)$ and $q = (4, 5)$ in $\reals^2$
: $5$
In the plane, the geodesic distance between $p$ and $q$ equals the Euclidean distance, because the straight segment from $p$ to $q$ stays in the plane.
Properties
- The geodesic distance is at least the Euclidean distance through the surrounding space, because a straight segment is the shortest of all paths, including those that leave the surface.
- In the plane (or in $\reals^n$), the geodesic distance is the Euclidean distance, because the straight segment stays in the space.
- A shortest path is called a geodesic. Geodesics need not be unique: every half great circle from the north pole to the south pole is a shortest path.
Examples
Each cell is the distance between the two points in that row.
The points $p = (1, 1)$ and $q = (4, 5)$ in $\reals^2$
The points $(1, 1)$ and $(4, 5)$ differ by $3$ in the first coordinate and $4$ in the second.
| Euclidean distance | $d_2(p, q) = \sqrt{3^2 + 4^2} = 5$ |
|---|---|
| Taxicab distance | $d_1(p, q) = 3 + 4 = 7$ |
| Chebyshev distance | $d_{\infty}(p, q) = \max(3, 4) = 4$ |
| discrete metric | $d(p, q) = 1$ |
| geodesic distance | $5$ |
The points $p = (0, 0)$ and $q = (2, 0)$ in $\reals^2$
Only the discrete metric differs.
| Euclidean distance | $d_2(p, q) = \sqrt{2^2 + 0^2} = 2$ |
|---|---|
| Taxicab distance | $d_1(p, q) = 2 + 0 = 2$ |
| Chebyshev distance | $d_{\infty}(p, q) = \max(2, 0) = 2$ |
| discrete metric | $d(p, q) = 1$ |
| geodesic distance | $2$ |
The points $p = (0, 0)$ and $q = (100, 100)$ in $\reals^2$
In the discrete metric, they are at distance $1$, the same as every two different points, so the discrete metric does not measure size at all.
| Euclidean distance | $d_2(p, q) = \sqrt{100^2 + 100^2} = 100 \sqrt{2} \approx 141.42$ |
|---|---|
| Taxicab distance | $d_1(p, q) = 100 + 100 = 200$ |
| Chebyshev distance | $d_{\infty}(p, q) = \max(100, 100) = 100$ |
| discrete metric | $d(p, q) = 1$ |
| geodesic distance | $100 \sqrt{2}$ |
The north pole $p = (0, 0, 1)$ and the point $q = (1, 0, 0)$ on the equator of the unit sphere in $\reals^3$
| Euclidean distance | $d_2(p, q) = \sqrt{1^2 + 0^2 + 1^2} = \sqrt{2} \approx 1.41$ |
|---|---|
| Taxicab distance | $d_1(p, q) = 1 + 0 + 1 = 2$ |
| Chebyshev distance | $d_{\infty}(p, q) = \max(1, 0, 1) = 1$ |
| discrete metric | $d(p, q) = 1$ |
| geodesic distance | $\frac{\pi}{2} \approx 1.57$ |
Notes
- The Euclidean, taxicab, and Chebyshev distances come from the Euclidean norm, the 1-norm, and the infinity norm, as $d(p, q) = \norm{p - q}$.
- The unit “circles” $\setdef{q \in \reals^2 \suchthat d(0, q) = 1}$ are a circle, a diamond, and a square, and for the discrete metric, every point other than $0$.
- Great-circle distance is the geodesic distance on a sphere. It does not come from a norm, because a sphere is not a vector space; see norm vs. metric vs. inner product.
- A distance needs only a set of points, not a vector space. The Euclidean, taxicab, and Chebyshev distances use the coordinates of $\reals^n$, the geodesic distance needs a surface (or manifold) along which to measure paths, and the discrete metric works on every set.