Chebyshev distance

The Chebyshev distance between two vectors or points a and b, with standard coordinates a_i and b_i, respectively, is D(a,b) = \max_i(|a_i - b_i|). This equals the limit of the Lp metrics: D(a,b)=\lim_{p \to \infty} \bigg( \sum_{i=1}^n \left| a_i - b_i \right|^p \bigg)^{1/p}, 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 a and b have Cartesian coordinates (x_1,y_1) and (x_2,y_2), their Chebyshev distance is D_{\rm Chebyshev} = \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. 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. == Properties ==

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 r, 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-p Minkowski distance, when p reaches infinity. == Applications ==

The Chebyshev distance is sometimes used in warehouse logistics, 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. ==Generalizations==

For the sequence space of infinite-length sequences of real or complex numbers, the Chebyshev distance generalizes to the \ell^\infty-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. ==See also==