Chebyshev distance
Template:Short description Template:About Template:Chess diagram small
In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or L∞ metric<ref>Template:Cite book</ref> is a metric defined on a real coordinate space where the distance between two points is the greatest of their differences along any coordinate dimension.<ref>Template:Cite book</ref> 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 one square on a chessboard to another equals the Chebyshev distance between the centers of the squares, if the squares have side length one, as represented in 2-D spatial coordinates with axes aligned to the edges of the board.<ref>Template:Cite book</ref> For example, the Chebyshev distance between f6 and e2 equals 4.
DefinitionEdit
The Chebyshev distance between two vectors or points x and y, with standard coordinates <math>x_i</math> and <math>y_i</math>, respectively, is
- <math>D(x,y) = \max_i(|x_i -y_i|).\ </math>
This equals the limit of the Lp metrics:
- <math>D(x,y)=\lim_{p \to \infty} \bigg( \sum_{i=1}^n \left| x_i - y_i \right|^p \bigg)^{1/p},</math>
hence it is also known as the L∞ metric.
Mathematically, the Chebyshev distance is a metric induced by the supremum norm or uniform norm. 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>, their Chebyshev distance is
- <math>D_{\rm Chebyshev} = \max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right ) .</math>
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.
On a chessboard, where one is using a discrete Chebyshev distance, rather than a continuous one, the circle of radius r is a square of side lengths 2r, measuring from the centers of squares, and thus each side contains 2r+1 squares; for example, the circle of radius 1 on a chess board is a 3×3 square.
PropertiesEdit
In one dimension, all Lp metrics are equal – they are just the absolute value of the difference.
The two dimensional Manhattan distance has "circles" i.e. level sets in the form of squares, with sides of length Template:Sqrtr, 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 (i.e. a linear transformation of) the planar Manhattan distance.
However, this geometric equivalence between L1 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: these are dual polyhedra, but among cubes, only the square (and 1-dimensional line segment) are self-dual polytopes. Nevertheless, it is true that in all finite-dimensional spaces the L1 and L∞ metrics are mathematically dual to each other.
On a grid (such as a chessboard), the points at a Chebyshev distance of 1 of a point are the Moore neighborhood of that point.
The Chebyshev distance is the limiting case of the order-<math>p</math> Minkowski distance, when <math>p</math> reaches infinity.
ApplicationsEdit
The Chebyshev distance is sometimes used in warehouse logistics,<ref>Template:Cite book</ref> as it effectively measures the time an overhead crane takes to move an object (as the crane can move on the x and y axes at the same time but at the same speed along each axis).
It is also widely used in electronic computer-aided manufacturing (CAM) applications, in particular, in optimization algorithms for these.
GeneralizationsEdit
For the sequence space of infinite-length sequences of real or complex numbers, the Chebyshev distance generalizes to the <math>\ell^\infty</math>-norm; this norm is sometimes called the Chebyshev norm. For the space of (real or complex-valued) functions, the Chebyshev distance generalizes to the uniform norm.