Chebyshev distance

This article is about the finite-dimensional vector space distance. For the function space norm, see uniform norm.
abcdefgh
8
a8 five
b8 four
c8 three
d8 two
e8 two
f8 two
g8 two
h8 two
a7 five
b7 four
c7 three
d7 two
e7 one
f7 one
g7 one
h7 two
a6 five
b6 four
c6 three
d6 two
e6 one
f6 white king
g6 one
h6 two
a5 five
b5 four
c5 three
d5 two
e5 one
f5 one
g5 one
h5 two
a4 five
b4 four
c4 three
d4 two
e4 two
f4 two
g4 two
h4 two
a3 five
b3 four
c3 three
d3 three
e3 three
f3 three
g3 three
h3 three
a2 five
b2 four
c2 four
d2 four
e2 four
f2 four
g2 four
h2 four
a1 five
b1 five
c1 five
d1 five
e1 five
f1 five
g1 five
h1 five
8
77
66
55
44
33
22
11
abcdefgh
The Chebyshev distance between two spaces on a chess board gives the minimum number of moves a 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 rank 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∞ metric[1] is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension.[2] 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.[3] For example, the Chebyshev distance between f6 and e2 equals 4.

Definition

The Chebyshev distance between two vectors or points p and q, with standard coordinates p_i and q_i, respectively, is

D_{\rm Chebyshev}(p,q) := \max_i(|p_i - q_i|).\

This equals the limit of the Lp metrics:

\lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k},

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_{\rm Chess} = \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 chess board, 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 also has circles 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 the planar Manhattan distance.

However, this 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.

The Chebyshev distance is sometimes used in warehouse logistics,[4] 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).

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.

See also

References

  1. ↑ Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0-521-59827-3.
  2. ↑ James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (2002). Handbook of Massive Data Sets. Springer. ISBN 1-4020-0489-3.
  3. ↑ David M. J. Tax, Robert Duin, and 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 and Diane Riopel (2005). Logistics Systems. Springer. ISBN 0-387-24971-0.

External links