| 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 | ||
Inmathematics,Chebyshev distance (orTchebychev distance),maximum metric, orL∞ metric[1] is ametric defined on areal coordinate space where thedistance between twopoints is the greatest of their differences along any coordinate dimension.[2] It is named afterPafnuty Chebyshev.
It is also known aschessboard distance, since in the game ofchess the minimum number of moves needed by aking to go from one square on achessboard 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.[3] For example, the Chebyshev distance between f6 and e2 equals 4.
The Chebyshev distance between two vectors or pointsa andb, with standard coordinates and, respectively, is
This equals the limit of theLp metrics:hence it is also known as the L∞ metric.
Mathematically, the Chebyshev distance is ametric induced by thesupremum norm oruniform norm. It is an example of aninjective metric.
In two dimensions, i.e.plane geometry, if the pointsa andb haveCartesian coordinates and, their Chebyshev distance is
Under this metric, acircle ofradiusr, which is the set of points with Chebyshev distancer 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 adiscrete Chebyshev distance, rather than a continuous one, the circle of radiusr 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.
In one dimension, all Lp metrics are equal – they are just the absolute value of the difference.
The two-dimensionalManhattan 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. alinear transformation of) the planar Manhattan distance.
However, this geometric equivalence between L1 and L∞ metrics does not generalize to higher dimensions. Asphere formed using the Chebyshev distance as a metric is acube with each face perpendicular to one of the coordinate axes, but a sphere formed usingManhattan distance is anoctahedron: these aredual polyhedra, but among cubes, only the square (and 1-dimensional line segment) areself-dualpolytopes. 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 theMoore neighborhood of that point.
The Chebyshev distance is the limiting case of the order-Minkowski distance, when reachesinfinity.
The Chebyshev distance is sometimes used inwarehouselogistics,[4] as it effectively measures the time anoverhead 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 electroniccomputer-aided manufacturing (CAM) applications, in particular, in optimization algorithms for these.
For thesequence space of infinite-length sequences of real or complex numbers, the Chebyshev distance generalizes to the-norm; this norm is sometimes called the Chebyshev norm. For the space of (real or complex-valued) functions, the Chebyshev distance generalizes to theuniform norm.
| Basic concepts | |||
|---|---|---|---|
| L1 spaces | |||
| L2 spaces | |||
| spaces | |||
| Maps | |||
| Inequalities | |||
| Results |
| ||
| Applications & related | |||