Misplaced Pages

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or L_∞ metric 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. 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. 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 ${\displaystyle x_{i}}$ and ${\displaystyle y_{i}}$, respectively, is

${\displaystyle D(x,y)=\max _{i}(|x_{i}-y_{i}|).\ }$

This equals the limit of the L_p metrics:

${\displaystyle D(x,y)=\lim _{p\to \infty }{\bigg (}\sum _{i=1}^{n}\left|x_{i}-y_{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 p and q have Cartesian coordinates ${\displaystyle (x_{1},y_{1})}$ and ${\displaystyle (x_{2},y_{2})}$, their Chebyshev distance is

${\displaystyle 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 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 √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 (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-${\displaystyle p}$ Minkowski distance, when ${\displaystyle 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. Many tools, such as plotting or drilling machines, photoplotter, etc. operating in the plane, are usually controlled by two motors in x and y directions, similar to the overhead cranes.

Generalizations

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

• King's graph
• Taxicab geometry

References

1. Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0-521-59827-3.
2. Abello, James M.; Pardalos, Panos M.; Resende, Mauricio G. C., eds. (2002). Handbook of Massive Data Sets. Springer. ISBN 1-4020-0489-3.
3. David M. J. Tax; Robert Duin; Dick De Ridder (2004). Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB. John Wiley and Sons. ISBN 0-470-09013-8.
4. André Langevin; Diane Riopel (2005). Logistics Systems. Springer. ISBN 0-387-24971-0.
5. Seitz, Charles L. (1989). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989. ISBN 9780262192828.

v t e Lp spaces
Basic concepts	Banach & Hilbert spaces L spaces Measure Lebesgue Measure space Measurable space/function Minkowski distance Sequence spaces
L spaces	Integrable function Lebesgue integration Taxicab geometry
L spaces	Bessel's Cauchy–Schwarz Euclidean distance Hilbert space Parseval's identity Polarization identity Pythagorean theorem Square-integrable function
${\displaystyle L^{\infty }}$ spaces	Bounded function Chebyshev distance Infimum and supremum Essential Uniform norm
Maps	Almost everywhere Convergence almost everywhere Convergence in measure Function space Integral transform Locally integrable function Measurable function Symmetric decreasing rearrangement
Inequalities	Babenko–Beckner Chebyshev's Clarkson's Hanner's Hausdorff–Young Hölder's Markov's Minkowski Young's convolution
Results	Marcinkiewicz interpolation theorem Plancherel theorem Riemann–Lebesgue Riesz–Fischer theorem Riesz–Thorin theorem For Lebesgue measure Isoperimetric inequality Brunn–Minkowski theorem Milman's reverse Minkowski–Steiner formula Prékopa–Leindler inequality Vitale's random Brunn–Minkowski inequality
Applications & related	Bochner space Fourier analysis Lorentz space Probability theory Quasinorm Real analysis Sobolev space *-algebra C*-algebra Von Neumann

• Distance
• Mathematical chess problems
• Metric geometry