Chebyshev distance

From Wikipedia, the free encyclopedia

In mathematics, the Chebyshev distance between two points p and q in Euclidean space with standard coordinates p_i and q_i respectively is

<math>D_{\rm Chess} = \max_i(|p_i - q_i|) = \lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k}</math>.

The Chebyshev distance is in fact a special case of the supremum norm, and is also known as chessboard distance or the L_∞ metric. It is an example of an injective metric.

In two dimensions, i.e. plane geometry, if the points p and q have Cartesian coordinates <math>(x_1,y_1)</math> and <math>(x_2,y_2)</math>, this becomes

<math>D_{\rm Chess} = \max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right ) .</math>

The "circle" of radius r in the Chebyshev metric is a square with side length 2r parallel to the coordinate axes. The two dimensional Manhattan distance also has circles in the form of squares, with side length √2r, at an angle of π/4 to the coordinate axes, so the planar Chebyshev distance can be viewed as equivalent by rotation and scaling to the planar Manhattan distance. However this equivalence between L₁ and L_∞ metrics does not generalize to higher dimensions.

The Chebyshev distance is named after Pafnuty Chebyshev. In chess, the distance between squares, in terms of moves necessary for a king, is given by the Chebyshev distance, hence the second name.