Editing Chebyshev distance

{{Short description|Mathematical metric}}
{{About|the distance in finite-dimensional spaces|the function space norm and metric|uniform norm}}
{{Chess diagram small
| tright
| 
|x5|x4|x3|x2|x2|x2|x2|x2
|x5|x4|x3|x2|x1|x1|x1|x2
|x5|x4|x3|x2|x1|kl|x1|x2
|x5|x4|x3|x2|x1|x1|x1|x2
|x5|x4|x3|x2|x2|x2|x2|x2
|x5|x4|x3|x3|x3|x3|x3|x3
|x5|x4|x4|x4|x4|x4|x4|x4
|x5|x5|x5|x5|x5|x5|x5|x5
| The discrete Chebyshev distance between two spaces on a [[chessboard]] gives the minimum number of moves a [[king (chess)|king]] requires to move between them. This is because a king can move diagonally, so that the jumps to cover the smaller distance parallel to a row or column is effectively absorbed into the jumps covering the larger. Above are the Chebyshev distances of each square from the square f6.
}}

In [[mathematics]], '''Chebyshev distance''' (or '''Tchebychev distance'''), '''maximum metric''', or '''L<sub>∞</sub> metric'''<ref>{{cite book | title = Modern Mathematical Methods for Physicists and Engineers | url = https://archive.org/details/modernmathematic0000cant | url-access = registration | author = Cyrus. D. Cantrell | isbn = 0-521-59827-3 | publisher = Cambridge University Press | year = 2000 }}</ref> is a [[Metric (mathematics)|metric]] defined on a [[real coordinate space]] where the [[distance]] between two [[point (geometry)|points]] is the greatest of their differences along any coordinate dimension.<ref>{{cite book
 | editor1-last = Abello | editor1-first = James M.
 | editor2-last = Pardalos | editor2-first = Panos M.
 | editor3-last = Resende | editor3-first = Mauricio G. C. | editor3-link = Mauricio Resende
 | isbn = 1-4020-0489-3
 | publisher = Springer
 | title = Handbook of Massive Data Sets
 | year = 2002}}</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 (chess)|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>{{cite book | title = Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB |author1=David M. J. Tax |author2=Robert Duin |author3=Dick De Ridder | isbn = 0-470-09013-8 | publisher = John Wiley and Sons | year = 2004}}</ref> For example, the Chebyshev distance between f6 and e2 equals 4.

== Definition ==
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 space|L<sub>''p''</sub> 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<sub>∞</sub> metric.

Mathematically, the Chebyshev distance is a [[metric (mathematics)|metric]] induced by the [[supremum norm]] or [[uniform norm]]. It is an example of an [[injective metric space|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 2''r'' 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 2''r,'' measuring from the centers of squares, and thus each side contains 2''r''+1 squares; for example, the circle of radius 1 on a chess board is a 3&times;3 square.

== Properties ==
[[File:Minkowski_distance_examples.svg|thumb|Comparison of Chebyshev, Euclidean and Manhattan distances for the hypotenuse of a 3-4-5 triangle on a chessboard]]
In one dimension, all L<sub>''p''</sub> 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<sub>1</sub> and L<sub>∞</sub> 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 polyhedra|self-dual]] [[polytope]]s. Nevertheless, it is true that in all finite-dimensional spaces the L<sub>1</sub> and L<sub>∞</sub> 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]].

== Applications ==

The Chebyshev distance is sometimes used in [[warehouse]] [[logistics]],<ref>{{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 }}</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. 

==Generalizations==
For the [[sequence space]] of infinite-length sequences of real or complex numbers, the Chebyshev distance generalizes to the [[L-infinity|<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]].

==See also==
*[[King's graph]]
*[[Taxicab geometry]]

==References==

{{reflist}}

{{Lp spaces}}

{{DEFAULTSORT:Chebyshev Distance}}

[[Category:Distance]]
[[Category:Mathematical chess problems]]
[[Category:Metric geometry]]