Chebyshev distance

The Chebyshev distance between two vectors or points x and y, with standard coordinates $x\_i$ and $y\_i$, respectively, is

:$D(x,y)\; =\; \backslash max\_i(|x\_i\; -y\_i|).\backslash$

This equals the limit of the L_p metrics:

:$D(x,y)=\backslash lim\_\{p\; \backslash to\; \backslash infty\}\; \backslash bigg(\; \backslash sum\_\{i=1\}^n\; \backslash left|\; x\_i\; -\; y\_i\; \backslash right|^p\; \backslash 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 p and q have Cartesian coordinates

$(x\_1,y\_1)$ and $(x\_2,y\_2)$, their Chebyshev distance is

:$D\_\{\backslash rm\; Chebyshev\}\; =\; \backslash max\; \backslash left\; (\; \backslash left\; |\; x\_2\; -\; x\_1\; \backslash right\; |\; ,\; \backslash left\; |\; y\_2\; -\; y\_1\; \backslash right\; |\; \backslash 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.

File:Minkowski_distance_examples.svg

In one dimension, all L_p 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 {{sqrt|2}}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 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: 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 L₁ 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.

The Chebyshev distance is sometimes used in warehouse logistics,{{cite book | title = Logistics Systems |author1=André Langevin |author2=Diane Riopel | publisher = Springer | year = 2005 | isbn = 0-387-24971-0 | url = https://books.google.com/books?id=9I8HvNfSsk4C&q=Chebyshev+distance++warehouse+logistics&pg=PA96 }} 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.

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

• King's graph
• Taxicab geometry

{{reflist}}

{{Lp spaces}}

{{DEFAULTSORT:Chebyshev Distance}}

Category:Distance

Category:Mathematical chess problems

Category:Metric geometry