Distance de Tchebychev

distance entre deux points donnée par la différence maximale entre leurs coordonnées sur une dimension

La distance de Tchebychev, distance de Chebyshev ou ∞-distance, est la distance entre deux points donnée par la différence maximale entre leurs coordonnées sur une dimension.

abcdefgh
8
cinq sur case blanche a8
quatre sur case noire b8
trois sur case blanche c8
deux sur case noire d8
deux sur case blanche e8
deux sur case noire f8
deux sur case blanche g8
deux sur case noire h8
cinq sur case noire a7
quatre sur case blanche b7
trois sur case noire c7
deux sur case blanche d7
un sur case noire e7
un sur case blanche f7
un sur case noire g7
deux sur case blanche h7
cinq sur case blanche a6
quatre sur case noire b6
trois sur case blanche c6
deux sur case noire d6
un sur case blanche e6
Roi blanc sur case noire f6
un sur case blanche g6
deux sur case noire h6
cinq sur case noire a5
quatre sur case blanche b5
trois sur case noire c5
deux sur case blanche d5
un sur case noire e5
un sur case blanche f5
un sur case noire g5
deux sur case blanche h5
cinq sur case blanche a4
quatre sur case noire b4
trois sur case blanche c4
deux sur case noire d4
deux sur case blanche e4
deux sur case noire f4
deux sur case blanche g4
deux sur case noire h4
cinq sur case noire a3
quatre sur case blanche b3
trois sur case noire c3
trois sur case blanche d3
trois sur case noire e3
trois sur case blanche f3
trois sur case noire g3
trois sur case blanche h3
cinq sur case blanche a2
quatre sur case noire b2
quatre sur case blanche c2
quatre sur case noire d2
quatre sur case blanche e2
quatre sur case noire f2
quatre sur case blanche g2
quatre sur case noire h2
cinq sur case noire a1
cinq sur case blanche b1
cinq sur case noire c1
cinq sur case blanche d1
cinq sur case noire e1
cinq sur case blanche f1
cinq sur case noire g1
cinq sur case blanche h1
8
77
66
55
44
33
22
11
abcdefgh
Distance discrète de Tchebychev de chaque case d'un échiquier par rapport au roi.

Étymologie

modifier

La distance de Tchebychev tient son nom du mathématicien russe Pafnouti Tchebychev.

Définition

modifier

Entre deux points A et B, de coordonnées respectives et , la distance de Tchebychev est définie par :

Autrement dit : c'est la distance associée à la norme « infini ».

Analogies

modifier

La distance de Tchebychev est équivalente à la distance de Minkowski (en) d'ordre infini.

Dans un automate cellulaire, les cellules à une distance de Tchebychev N d'une autre constituent son voisinage de Moore d'ordre N.

Calcul numérique

modifier

Le calcul d'une distance de Tchebychev ne fait intervenir que des soustractions, des valeurs absolues (donc des changements de signe) et des comparaisons (recherche de la valeur maximale). Elle est donc moins sujette aux erreurs numériques qu'une distance quadratique, qui elle calcule des sommes de carrés. De plus, elle sera calculée plus rapidement.