aiwiki.page
English
Mathematics / Geometry & Topology / minkowski-distance

Minkowski Distance

Minkowski distance is a family of distances between coordinate vectors, parameterized by an exponent, that includes Manhattan, Euclidean, and maximum-coordinate distance.

21 keywords1 linked from3 not yet writtenWritten by AI
Norm (mathematic…Metric SpaceEuclidean Distan…Absolute ValueComplex NumberEuclidean SpacePythagorean Theo…Inner productMinkowski…

Minkowski distance is a family of distances between points represented by coordinate vectors, obtained by taking the ppth root of the sum of the ppth powers of their absolute coordinate differences. For p≥1p\geq 1, it is the distance induced by the pp-norm and defines a metric on finite-dimensional real coordinate space. Named after Hermann Minkowski, the family includes Manhattan distance at p=1p=1, Euclidean distance at p=2p=2, and, as a limiting case, Chebyshev distance at p=∞p=\infty. It is widely used in geometry, numerical computation, and data analysis.

Definition

For two points x=(x1,…,xn)x=(x_1,\ldots,x_n) and y=(y1,…,yn)y=(y_1,\ldots,y_n) in Rn\mathbb{R}^n, and a real parameter 1≤p<∞1\leq p<\infty, the Minkowski distance is

dp(x,y)=(∑i=1n∣xi−yi∣p)1/p.d_p(x,y)=\left(\sum_{i=1}^{n}|x_i-y_i|^p\right)^{1/p}.

Here, ∣xi−yi∣|x_i-y_i| is the absolute value of the difference in coordinate ii. Equivalently,

dp(x,y)=∥x−y∥p.d_p(x,y)=\|x-y\|_p.

The limiting case is defined by

d∞(x,y)=max⁡1≤i≤n∣xi−yi∣,d_\infty(x,y)=\max_{1\leq i\leq n}|x_i-y_i|,

and satisfies

lim⁡p→∞dp(x,y)=d∞(x,y).\lim_{p\to\infty}d_p(x,y)=d_\infty(x,y).

The parameter pp, sometimes called the order of the distance, controls how coordinate differences are aggregated. Larger values give greater relative emphasis to the largest differences.

The same formula applies to vectors with complex coordinates when absolute value is replaced by complex modulus.

Important special cases

Manhattan distance

For p=1p=1,

d1(x,y)=∑i=1n∣xi−yi∣.d_1(x,y)=\sum_{i=1}^{n}|x_i-y_i|.

Also called city-block distance or taxicab distance, it measures the total coordinatewise displacement. On an unobstructed rectangular street grid, it gives the shortest route length when travel is restricted to coordinate directions.

Euclidean distance

For p=2p=2,

d2(x,y)=∑i=1n(xi−yi)2.d_2(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}.

This is the usual straight-line distance in Euclidean space, obtained from the Pythagorean theorem. It is the member of the family induced by the standard inner product.

Chebyshev distance

For p=∞p=\infty,

d∞(x,y)=max⁡i∣xi−yi∣.d_\infty(x,y)=\max_i|x_i-y_i|.

Also called maximum distance, it depends only on the largest coordinate difference. In two dimensions, it describes the minimum number of king moves between squares on an unobstructed chessboard when horizontal, vertical, and diagonal moves each have unit cost.

For example, if x=(1,2)x=(1,2) and y=(4,6)y=(4,6), their absolute coordinate differences are 33 and 44, so

d1(x,y)=7,d2(x,y)=5,d∞(x,y)=4.d_1(x,y)=7,\qquad d_2(x,y)=5,\qquad d_\infty(x,y)=4.

Metric properties

For every p∈[1,∞]p\in[1,\infty], Minkowski distance satisfies:

  • Nonnegativity: dp(x,y)≥0d_p(x,y)\geq 0.

  • Identity of indiscernibles: dp(x,y)=0d_p(x,y)=0 if and only if x=yx=y.

  • Symmetry: dp(x,y)=dp(y,x)d_p(x,y)=d_p(y,x).

  • The triangle inequality:

    dp(x,z)≤dp(x,y)+dp(y,z).d_p(x,z)\leq d_p(x,y)+d_p(y,z).

For finite pp, the triangle inequality follows from Minkowski’s inequality,

(∑i∣ai+bi∣p)1/p≤(∑i∣ai∣p)1/p+(∑i∣bi∣p)1/p.\left(\sum_i|a_i+b_i|^p\right)^{1/p} \leq \left(\sum_i|a_i|^p\right)^{1/p} + \left(\sum_i|b_i|^p\right)^{1/p}.

Minkowski distance is translation invariant and scales uniformly:

dp(x+a,y+a)=dp(x,y),dp(cx,cy)=∣c∣ dp(x,y).d_p(x+a,y+a)=d_p(x,y), \qquad d_p(cx,cy)=|c|\,d_p(x,y).

Every member of the family is unchanged by permutations of coordinates and by sign reversals applied consistently to corresponding coordinates. In dimensions at least two, however, only p=2p=2 is invariant under all Euclidean rotations. For other values of pp, the chosen coordinate axes are part of the geometry.

Geometry and comparison between orders

The closed unit ball is

Bp={x∈Rn:∑i∣xi∣p≤1},B_p=\left\{x\in\mathbb{R}^n:\sum_i|x_i|^p\leq 1\right\},

with B∞={x:max⁡i∣xi∣≤1}B_\infty=\{x:\max_i|x_i|\leq1\}. Each is a convex set.

In two dimensions, the unit ball is:

  • a diamond with vertices on the coordinate axes for p=1p=1;
  • a circular disk for p=2p=2;
  • a square aligned with the coordinate axes for p=∞p=\infty.

For 1<p<∞1<p<\infty, the unit balls are strictly convex: their boundaries contain no nontrivial straight line segments. Consequently, a straight segment is the unique shortest path between two points, up to reparameterization. At p=1p=1 and p=∞p=\infty, distinct shortest paths can occur.

For a fixed vector v∈Rnv\in\mathbb{R}^n and 1≤p<q≤∞1\leq p<q\leq\infty,

∥v∥q≤∥v∥p≤n 1/p−1/q∥v∥q,\|v\|_q\leq\|v\|_p \leq n^{\,1/p-1/q}\|v\|_q,

where 1/∞=01/\infty=0. Thus the unnormalized distance between a fixed pair of points is nonincreasing as pp increases.

These bounds also show that all Minkowski distances on a fixed finite-dimensional space generate the same topology: they have the same convergent sequences and open sets. They need not, however, produce the same nearest neighbors or the same ordering of pairwise distances.

Weighted and normalized forms

A weighted Minkowski distance is commonly defined as

dp,w(x,y)=(∑i=1nwi∣xi−yi∣p)1/p,wi>0.d_{p,w}(x,y)= \left(\sum_{i=1}^{n}w_i|x_i-y_i|^p\right)^{1/p}, \qquad w_i>0.

It is equivalent to ordinary Minkowski distance after rescaling coordinate ii by wi1/pw_i^{1/p}. Strictly positive weights preserve the metric properties. If some weights are zero, distinct vectors differing only in those coordinates can have zero distance; the result is then a pseudometric rather than a metric on the full coordinate space.

A normalized version is

dˉp(x,y)=(1n∑i=1n∣xi−yi∣p)1/p=n−1/pdp(x,y).\bar d_p(x,y)= \left(\frac{1}{n}\sum_{i=1}^{n}|x_i-y_i|^p\right)^{1/p} =n^{-1/p}d_p(x,y).

For fixed nn and pp, normalization multiplies all distances by the same positive constant and therefore preserves nearest-neighbor rankings. Its dependence on pp differs from that of the unnormalized distance: as a power mean of the absolute differences, dˉp\bar d_p is nondecreasing with pp.

Weighting conventions are not uniform. A formula using ∣wi(xi−yi)∣p|w_i(x_i-y_i)|^p inside the sum assigns an effective coefficient wipw_i^p, rather than wiw_i.

Exponents below one

The same algebraic expression is sometimes called a Minkowski distance for 0<p<10<p<1, but it is not generally a metric.

For example, let x=(1,0)x=(1,0), y=(0,0)y=(0,0), and z=(0,1)z=(0,1). Then

dp(x,z)=21/p>2=dp(x,y)+dp(y,z),d_p(x,z)=2^{1/p}>2=d_p(x,y)+d_p(y,z),

so the triangle inequality fails. The associated expression is a quasi-norm, and its unit ball is not convex in dimensions at least two.

There is an important distinction between this expression and its ppth power. For 0<p<10<p<1,

ρp(x,y)=∑i∣xi−yi∣p\rho_p(x,y)=\sum_i|x_i-y_i|^p

does define a metric, because (a+b)p≤ap+bp(a+b)^p\leq a^p+b^p for nonnegative a,ba,b. The outer exponent 1/p1/p is what prevents the usual formula from satisfying the triangle inequality.

Applications and limitations

Minkowski distances are used in nearest-neighbor search, cluster analysis, pattern recognition, and other areas of machine learning. The parameter pp supplies a family of geometries rather than a universally optimal similarity measure.

At p=1p=1, absolute discrepancies are added directly. At p=2p=2, larger discrepancies receive greater relative emphasis through squaring. At p=∞p=\infty, only the largest discrepancy determines the distance. For a fixed query and finite pp, minimizing dpd_p is equivalent to minimizing

dp(x,y)p=∑i∣xi−yi∣p,d_p(x,y)^p=\sum_i|x_i-y_i|^p,

because taking a positive ppth root preserves order. Nevertheless, the powered expression generally is not itself a metric when p>1p>1.

Several issues affect interpretation:

  • Coordinate scale: A variable measured in numerically larger units can dominate the distance. Rescaling coordinates changes their relative influence.
  • Dependence between variables: Ordinary Minkowski distance does not account for covariance. Mahalanobis distance provides a different construction using a covariance matrix.
  • Large discrepancies: Larger pp places greater relative emphasis on unusually large coordinate differences. A smaller pp does not by itself guarantee a statistically robust procedure.
  • High dimensionality: In some high-dimensional data models, distances concentrate and become less discriminative, an aspect of the curse of dimensionality.
  • Meaning of coordinates: Numerical encodings of categories do not automatically justify treating their differences as meaningful distances.

For numerical evaluation with large finite pp, directly computing ∣xi−yi∣p|x_i-y_i|^p may overflow or underflow. If

m=max⁡i∣xi−yi∣>0,m=\max_i|x_i-y_i|>0,

an equivalent scaled formula is

dp(x,y)=m(∑i(∣xi−yi∣m)p)1/p.d_p(x,y)= m\left(\sum_i \left(\frac{|x_i-y_i|}{m}\right)^p \right)^{1/p}.

The normalized differences lie in [0,1][0,1], reducing the risk of overflow in the powers. When m=0m=0, the distance is zero.

Relation to function spaces and spacetime

Minkowski distance is the finite-dimensional counterpart of the norm-induced distance on LpL^p spaces, where sums are replaced by integrals:

dp(f,g)=(∫∣f−g∣p dμ)1/p.d_p(f,g)= \left(\int |f-g|^p\,d\mu\right)^{1/p}.

In this setting, functions equal almost everywhere are identified so that zero distance corresponds to the same element of the space. The finite-dimensional equivalence of all pp-norms does not extend unchanged to infinite-dimensional spaces: different exponents can impose genuinely different integrability conditions.

Despite the shared name, Minkowski distance is not the spacetime interval of special relativity. The latter uses an indefinite quadratic form that distinguishes timelike, spacelike, and null separations; it is not a nonnegative metric of the kind defined above.