Chebyshev distance

Chebyshev distance
Solid white.svg a b c d e f g h Solid white.svg
8 a8 five b8 four c8 three d8 two e8 two f8 two g8 two h8 two 8
7 a7 five b7 four c7 three d7 two e7 one f7 one g7 one h7 two 7
6 a6 five b6 four c6 three d6 two e6 one f6 white king g6 one h6 two 6
5 a5 five b5 four c5 three d5 two e5 one f5 one g5 one h5 two 5
4 a4 five b4 four c4 three d4 two e4 two f4 two g4 two h4 two 4
3 a3 five b3 four c3 three d3 three e3 three f3 three g3 three h3 three 3
2 a2 five b2 four c2 four d2 four e2 four f2 four g2 four h2 four 2
1 a1 five b1 five c1 five d1 five e1 five f1 five g1 five h1 five 1
Solid white.svg a b c d e f g h Solid white.svg
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.



The Chebyshev distance between two vectors or points p and q, with standard coordinates pi and qi, 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 (x1,y1) and (x2,y2), 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.


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 polyhedra.

The Chebyshev distance is sometimes used in warehouse logistics.[4]

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


  1. ^ Cyrus. D. Cantrell (2000). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0521598273. 
  2. ^ James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (2002). Handbook of Massive Data Sets. Springer. ISBN 1402004893. 
  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 0470090138. 
  4. ^ André Langevin and Diane Riopel (2005). Logistics Systems. Springer. ISBN 0387249710. 

External links

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Distance — This article is about distance in the mathematical or physical sense. For other senses of the term, see distance (disambiguation). Proximity redirects here. For the 2001 film, see Proximity (film). Distance (or farness) is a numerical description …   Wikipedia

  • Chebyshev's inequality — For the similarly named inequality involving series, see Chebyshev s sum inequality. In probability theory, Chebyshev’s inequality (also spelled as Tchebysheff’s inequality) guarantees that in any data sample or probability distribution, nearly… …   Wikipedia

  • Pafnuty Chebyshev — Chebyshev redirects here. For other uses, see Chebyshev (disambiguation). Pafnuty Chebyshev Pafnuty Lvovich Chebyshev Born May 16, 1821 …   Wikipedia

  • Minkowski distance — The Minkowski distance is a metric on Euclidean space which can be considered as a generalization of both the Euclidean distance and the Manhattan distance. Definition The Minkowski distance of order p between two points is defined as: The… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Taxicab geometry — versus Euclidean distance: In taxicab geometry all three pictured lines (red, blue, and yellow) have the same length (12) for the same route. In Euclidean geometry, the green line has length 6×√2 ≈ 8.48, and is the unique shortest path …   Wikipedia

  • List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history …   Wikipedia

  • List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by …   Wikipedia

  • Scientific phenomena named after people — This is a list of scientific phenomena and concepts named after people (eponymous phenomena). For other lists of eponyms, see eponym. NOTOC A* Abderhalden ninhydrin reaction Emil Abderhalden * Abney effect, Abney s law of additivity William de… …   Wikipedia

  • Uniform norm — This article is about the function space norm. For the finite dimensional vector space distance, see Chebyshev distance. The black square is the set of points in R2 where the sup norm equals a fixed non zero constant. In mathematical analysis,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”