Chebyshev distance

From Wikipedia, the free encyclopedia

The Chebyshev distance between two spaces on a chess board is the number of moves a king requires to move between them. Above are the Chebyshev distances of each square from the square f6.

In mathematics, Chebyshev distance (or Tchebychev distance) is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension.^[1] It is named after Pafnuty Chebyshev. It is also known as chessboard distance, since in the game of chess the minimum number of moves needed by a king to go from any square on a chessboard to some other square is proportional to the Chebyshev distance between those squares in two dimensions.^[2]

The Chebyshev distance between two vectors or points p and q, with standard coordinates p_i and q_i, respectively, is

$D_{\rm Chebyshev} = \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}.$

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

In two dimensions, i.e. plane geometry, if the points p and q have Cartesian coordinates $(x 1, y 1)$ and $(x 2, y 2)$ , their Chebyshev distance is

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

Under this metric, a circle of radius r, which is the set of points with Chebyshev distance r from a center point, is a square whose sides have the length 2r and are parallel to the coordinate axes. The two dimensional Manhattan distance also has circles in the form of squares, with sides of length √2r, oriented at an angle of π/4 (45°) 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. A sphere formed using the Chebyshev distance as a metric is a cube with each face perpendicular to one of the coordinate axes, but a sphere formed using Manhattan distance is an octahedron.

The Chebyshev distance is sometimes used in warehouse logistics.^{[citation needed]}

[edit] See also

[edit] References

^ James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (2002). Handbook of Massive Data Sets. Springer. ISBN 1402004893.
^ David M. J. Tax, Robert Duin, and Dick De Ridder (2004). Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB. John Wiley and Sons. ISBN 0470090138.
^ Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0521598273.