Distance de Manhattan

Distance de Manhattan (chemins rouge, jaune et bleu) contre distance euclidienne en vert.

La distance de ManhattanModèle:,, appelée aussi taxi-distance, est la distance entre deux points parcourue par un taxi lorsqu'il se déplace dans une ville où les rues sont agencées selon un réseau ou quadrillage. Un taxi-chemin est le trajet fait par un taxi lorsqu'il se déplace d'un nœud du réseau à un autre en utilisant les déplacements horizontaux et verticaux du réseau.

Définition

Entre deux points A et B, de coordonnées respectives $(X_{A},Y_{A})$ et $(X_{B},Y_{B})$, la distance de Manhattan est définie par :

$d(A,B)=|X_{B}-X_{A}|+|Y_{B}-Y_{A}|$

Autrement dit, c'est la distance associée à la norme 1.

Propriétés

On montre que si l'on oriente le réseau et que l'on définit des déplacements élémentaires positifs et négatifs, la distance de Manhattan est indépendante du chemin parcouru à l'intérieur d'un réseau fini. Ainsi, sur l'image de droite, la distance entre les deux points noirs, qu'on les joigne par les chemins rouge, bleu ou jaune, est identique (et égale à 12).